Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 158, средняя оценка - 4.62
coreshok
3 / 3 / 0
Регистрация: 23.12.2011
Сообщений: 55
#1

Как выразить условие в операторе if для нахождения простого числа - C++

04.07.2012, 21:15. Просмотров 20791. Ответов 50
Метки нет (Все метки)

Приветствую вас!Уважаемые, подскажите пожалуйста как выразить условие в операторе if для нахождения простого числа, с помощью логических и операторов отношений.Если это возможно.Без массивов.Мне нужна просто маленькая подсказка, а остальное я хочу сам допетрить.В голове все знаю и понимаю как эти числа находятся, но не могу выразить в алгоритме кода .Язык С++.Заранее благодарен!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.07.2012, 21:15     Как выразить условие в операторе if для нахождения простого числа
Посмотрите здесь:
Использование второй функции для нахождения простого числа и её ошибки C++
C++ Каково будет условие вывода на экран простого числа( оно делится только на 1 и на себя)
C++ Условие в операторе switch
C++ Как выразить из числа Arc tg
Функция для простого числа C++
как правильно в программке записать условие нахождения бесконечности? C++
написать программу для прверки простого числа. язык программировние С C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
diagon
Higher
1928 / 1194 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
06.07.2012, 14:38     Как выразить условие в операторе if для нахождения простого числа #21
Цитата Сообщение от Catstail Посмотреть сообщение
т.е. программа будет всегда хэшировать по одному основанию? Не убеждает...
А зачем хешировать по нескольким основаниям?
В любом случае, основание можно передавать как параметр шаблона.
Например(набросал по быстрому, проверку на простоту содрал у soon, свою писать было лень).
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <iostream>
 
template <std::size_t N, std::size_t Current>
struct _Prime
{
    static const bool is_prime =    (
                                        (N % Current) ? 
                                            (_Prime<N, Current - 1>::is_prime) :
                                            (false)
                                    );
};
 
template <std::size_t N>
struct _Prime<N, 1>
{
    static const bool is_prime = true;
};
 
template <std::size_t N>
struct _Prime<N, 0>
{
    static const bool is_prime = true;
};
 
template <std::size_t N>
struct Prime
{
    static const bool is_prime = _Prime<N, N / 2>::is_prime;
};
 
template <>
struct Prime<1>
{
    static const bool is_prime = false;
};
 
template <>
struct Prime<0>
{
    static const bool is_prime = false;
};
 
template < int P > 
class hash
{
public:
 
    hash()
    {
        static_assert( Prime< P >::is_prime, "base must be prime");
    }
    
    template< class FwdIt >
    unsigned long long operator () (FwdIt begin, FwdIt end) const
    {
        unsigned long long res = 0;
        
        for (int p_pow = 1; begin != end; ++begin)
        {
            res += (*begin - 'a' + 1) * p_pow;
            p_pow *= P;
        }
        
        return res;
    }   
};
 
int main()
{
    hash< 31 > a;
    hash< 17 > b;
    //hash< 4 > c;  //если раскомментить, то будет ошибка компиляции
    
    std::string str = "abc";
    std::cout << a( str.begin(), str.end() ) << std::endl;
    std::cout << b( str.begin(), str.end() ) << std::endl;  
}
Результат: http://liveworkspace.org/code/4c2701...1d8a946ca21e29
Catstail
Модератор
22510 / 10915 / 1774
Регистрация: 12.02.2012
Сообщений: 18,061
06.07.2012, 14:57     Как выразить условие в операторе if для нахождения простого числа #22
чтобы не превращать дискуссию в "holly war", предлагаю поставить точку. Ибо:
1) Ваш способ имеет право на существование
2) выч. ресурсы он экономит в столь мизерном количестве, что этой экономией можно пренебречь...
coreshok
3 / 3 / 0
Регистрация: 23.12.2011
Сообщений: 55
06.07.2012, 14:59  [ТС]     Как выразить условие в операторе if для нахождения простого числа #23
Интересная дискуссия развернулась вокруг казалось бы простого вопроса,просто битва титанов.Я нервно курю в сторонке.
diagon
Higher
1928 / 1194 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
06.07.2012, 15:00     Как выразить условие в операторе if для нахождения простого числа #24
Цитата Сообщение от Catstail Посмотреть сообщение
чтобы не превращать дискуссию в "holly war", предлагаю поставить точку
Тут не холивар, и дело не только в экономии ресурсов. Ошибка времени компиляции всегда лучше ошибки времени выполнения. Поэтому такой вариант не просто имеет право на существование, но и является оптимальным.
Catstail
Модератор
22510 / 10915 / 1774
Регистрация: 12.02.2012
Сообщений: 18,061
06.07.2012, 15:05     Как выразить условие в операторе if для нахождения простого числа #25
Ладно. Но как только нужно проверить заранее неизвестное к-во чисел (или даже одно, но заранее не известное) - то способ бесполезен. Поэтому на меня он впечатления не производит.

В подтексте здесь, вне всякого сомнения - "демонстрация крутизны". Но лично я считаю, что пример и в этом смысле неудачен. С моей точки зрения "круто" это:

1) решение задачи способом в n раз короче

или

2) решение задачи способом в n раз производительнее

(а если не "или", а "И", да еще и прозрачно - то это уже гениальность)

А то, что вы так защищаете - это просто "игра ума"...
soon
2540 / 1305 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
06.07.2012, 15:18     Как выразить условие в операторе if для нахождения простого числа #26
Цитата Сообщение от Catstail Посмотреть сообщение
В подтексте здесь, вне всякого сомнения - "демонстрация крутизны".

Не по теме:

Подтекстом здесь является, вне всякого сомнения, надежда на получение внятной критики по коду. Которой, кстати, еще не было(критика типа "это хрень, run-time алгоритмы лучше по определению" не принимается, поскольку в данный момент времени меня интересует compile-time).
Все, теперь я точно отписался от темы.

Catstail
Модератор
22510 / 10915 / 1774
Регистрация: 12.02.2012
Сообщений: 18,061
06.07.2012, 15:38     Как выразить условие в операторе if для нахождения простого числа #27
Ох... Вы просто не услышали критику. С моей точки зрения код по объему преимуществ не имеет, по прозрачности - тоже. Преимущество в производительности - ничтожно. Что ещё?
coreshok
3 / 3 / 0
Регистрация: 23.12.2011
Сообщений: 55
06.07.2012, 16:40  [ТС]     Как выразить условие в операторе if для нахождения простого числа #28
Купил программист на базаре куропатку и отправился домой, предвкушая как он придет, приготовит и съест ее. Но вдруг на полдороги куропатка встрепенулась и заговорила с ним человеческим голосом
- Программист, отпусти меня а я расскажу тебе три важных правила, которые несомненно помогут тебе в жизни. Программист удивился такому чуду, и тут же пообещал отпустить птицу.
- Первое, сказала куропатка, ты никогда не должен верить всякой ерунде, кто бы тебе не говорил ее, хоть сам Бил Гейтс.
- Второе, ты никогда не должен делать того, чего ты сделать не сможешь.
- Третье, если сделал доброе дело, не сожалей об этом.
Сказала это куропатка, выпорхнула из рук программиста и уселась на ветке дерева. Здорово, подумал программист, будет о чем рассказать друзьям в пабе. А куропатка сидит на ветке, приглаживает перышки, и не улетает, а глядит на программиста. И вдруг произносит:
- Ну и дурак ты программист! У меня в желудке большой бриллиант. Если бы ты не слушал меня, то когда бы начал меня готовить, то нашел бы его. Потом бы продал этот бриллиант, купил бы себе комфортную повозку Toyota, большой дом c верандой, самый мощный компьютер, провел бы туда быстрый интернет, завел бы себе красивую женщину и был бы счастлив.
Услышал этот программист, выругался в сердцах, и полез быстрее на дерево ловить куропатку. Дерево было высокое, ветвистое, конечно же программист не поймал куропатку, а упал вниз весь ободравшийся и оцарапанный. Подлетает к нему куропатка и говорит:
- ты так ничего и не понял, программист, из тех трех правил что я тебе говорила. Первое: вот подумай сам, откуда у меня в желудке может взяться бриллианту, разве это не ерунда? Второе: зачем ты полез на это дерево, ведь сразу было понятно что ты не залезешь на него? Третье: ты сожалел о сделанном добром деле и от этого все твои беды.
Сказала это и улетела, а программист еще долго размышляя сидел под деревом .
Кто не понял, мораль этой притчи совсем не в трех банальных правилах, произнесенных к тому же птицей, а в том, что человек так устроен, что какие бы полезные советы ему не давали, он все равно не будет следовать им до тех пор пока не постигнет их полезность на своей шкуре.
RASHFor
6 / 6 / 0
Регистрация: 12.02.2012
Сообщений: 224
06.07.2012, 16:57     Как выразить условие в операторе if для нахождения простого числа #29
А я хотел бі разобраться с примером sooon`a . уменя какой то странный вывод:
Миниатюры
Как выразить условие в операторе if для нахождения простого числа  
coreshok
3 / 3 / 0
Регистрация: 23.12.2011
Сообщений: 55
06.07.2012, 17:23  [ТС]     Как выразить условие в операторе if для нахождения простого числа #30
Все работает, все числа выводятся!

Добавлено через 6 минут
Пардон,оказывается точно не работает.Не тот код скомпилировал.
rinat_w
89 / 85 / 4
Регистрация: 13.11.2011
Сообщений: 192
Завершенные тесты: 1
06.07.2012, 17:47     Как выразить условие в операторе if для нахождения простого числа #31
Если учесть что любое простое число большее трех можно представить в виде 6k±1 можно сократить время выполнения алгоритмов в почти шесть раз:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
bool isprime(int n){
     for (int i=2; i<=n/2; i++)
         if (n%i==0) return false;
     return true;
}
int main(){
    using namespace std;
    int n;
    cout<<"n="; cin>>n;
    cout<<"Prime numbers 1.."<<n<<":\n"<<2<<((n>2)?" 3":"");
    if (n>3){
       for (int i=6; i<=n; i+=6){
           if (isprime(i-1)) cout<<" "<<i-1;
           if (isprime(i+1) && i+1<=n) cout<<" "<<i+1;
       }
    }
    cout<<endl; system("pause");
    return 0;
}
coreshok
3 / 3 / 0
Регистрация: 23.12.2011
Сообщений: 55
06.07.2012, 18:12  [ТС]     Как выразить условие в операторе if для нахождения простого числа #32
Числа 2 и 3 тоже простые.
Catstail
Модератор
22510 / 10915 / 1774
Регистрация: 12.02.2012
Сообщений: 18,061
06.07.2012, 18:16     Как выразить условие в операторе if для нахождения простого числа #33
Хочу сказать - идея использовать разложение 6k+1 - реальное алгоритмическое преимущество. С моей точки зрения это - действительно круто. rinat_w-молодец!
coreshok
3 / 3 / 0
Регистрация: 23.12.2011
Сообщений: 55
06.07.2012, 18:26  [ТС]     Как выразить условие в операторе if для нахождения простого числа #34
system("pause")- это что, функция с аргументом.Почему компилятор выдает ошибку что функция не за декларирована т.е.не объявлена.Если ее за комментировать, то все работает.
diagon
Higher
1928 / 1194 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
06.07.2012, 18:26     Как выразить условие в операторе if для нахождения простого числа #35
Цитата Сообщение от Catstail Посмотреть сообщение
Хочу сказать - идея использовать разложение 6k+1 - реальное алгоритмическое преимущество.
С такой реализацией все равно квадратичная сложность получается, уменьшается только константа.
Хотя для очень больших чисел можно применять, если сделать нормальную проверку на простоту.

А я хотел бі разобраться с примером sooon`a . уменя какой то странный вывод:
Вы бы для начала посмотрели в main этого кода.
Catstail
Модератор
22510 / 10915 / 1774
Регистрация: 12.02.2012
Сообщений: 18,061
06.07.2012, 18:27     Как выразить условие в операторе if для нахождения простого числа #36
Я в курсе... Но в 6 раз - тоже неплохо! Вот от этого я бы не стал отказываться, т.к. польза РЕАЛЬНА.
coreshok
3 / 3 / 0
Регистрация: 23.12.2011
Сообщений: 55
06.07.2012, 18:44  [ТС]     Как выразить условие в операторе if для нахождения простого числа #37
Ребята, что значит использовать разложение 6k+1?
Catstail
Модератор
22510 / 10915 / 1774
Регистрация: 12.02.2012
Сообщений: 18,061
06.07.2012, 18:46     Как выразить условие в операторе if для нахождения простого числа #38
При просеивании чисел - брать только числа вида 6k+1 или 6k-1. Остальные проверять нет смысла - они точно не простые.
coreshok
3 / 3 / 0
Регистрация: 23.12.2011
Сообщений: 55
06.07.2012, 19:07  [ТС]     Как выразить условие в операторе if для нахождения простого числа #39
Благодарю! Это те условия которые описаны в операторах if в цикле for в главной функции.Интересный код.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.07.2012, 21:43     Как выразить условие в операторе if для нахождения простого числа
Еще ссылки по теме:
функции для вычисления среднего значения и определения простого числа C++
C++ Создать функции для вычисления среднего значения и определения простого числа.
Составить программу для нахождения числа, которое образуется из данного натурального числа при записи его цифр в обратном порядке C++
C++ Программа для нахождения числа
C++ Макрос для нахождения наибольшего числа

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
PSIAlt
86 / 86 / 8
Регистрация: 19.06.2012
Сообщений: 245
06.07.2012, 21:43     Как выразить условие в операторе if для нахождения простого числа #40
Цитата Сообщение от rinat_w Посмотреть сообщение
Если учесть что любое простое число большее трех можно представить в виде 6k±1 можно сократить время выполнения алгоритмов в почти шесть раз:
Спасибо, отличный вариант. Правда время сокращается в 3 раза, а не 6, но это тоже дофига))

Предлагаю совместить с решетом эратосфена, улучшенный вариант=)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <cmath>
#include <vector>
 
std::vector<int> primes;
 
bool isprime(int n){
    int nm = sqrt(n)+1;
    for( auto &i : primes )
        if (n%i==0) return false;
    return true;
}
int main(){
    using namespace std;
    int n;
    cout << "n=";
    cin>>n;
    primes.reserve( n/3+1 );
    cout << "Prime numbers 1.." << n << ":\n" << 2 << ((n>2)?" 3":"");
    if( n>3 ) {
       for( int i=6; i<=n; i+=6 ) {
           if( isprime(i-1) ) {
               cout<<" "<<i-1;
               primes.push_back(i-1);
            }
           if( isprime(i+1) && i+1<=n ) {
                cout<<" "<<i+1;
                primes.push_back(i+1);
           }
       }
    }
    cout<<endl;
    system("pause");
    return 0;
}
Yandex
Объявления
06.07.2012, 21:43     Как выразить условие в операторе if для нахождения простого числа
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru