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

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

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

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

04.07.2012, 21:15. Просмотров 20569. Ответов 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++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
rinat_w
89 / 85 / 4
Регистрация: 13.11.2011
Сообщений: 192
Завершенные тесты: 1
06.07.2012, 22:33     Как выразить условие в операторе if для нахождения простого числа #41
PSIAlt, чето я немного не понял а где решето эратосфена?
PSIAlt
86 / 86 / 8
Регистрация: 19.06.2012
Сообщений: 245
06.07.2012, 23:00     Как выразить условие в операторе if для нахождения простого числа #42
Ну любое не-простое число так или иначе делится на простое. Поэтому найденные простые числа мы складываем в primes и в дальнейшем при проверке на простость делим только на числа из этого списка. 2 и 3 не кладем т.к. эти числа не могут попасть в проверку by design
diagon
Higher
1926 / 1192 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
07.07.2012, 07:29     Как выразить условие в операторе if для нахождения простого числа #43
Цитата Сообщение от PSIAlt Посмотреть сообщение
Предлагаю совместить с решетом эратосфена, улучшенный вариант=)
У вас тут нету решета Эратосфена, и это ни разу не улучшенный вариант.
Я сейчас попробовал запустить ваш код для n = 10^8, 3 минуты ждал результата, не дождался.

Затем написал простой перебор чисел вида 6k+-1, для проверки на простоту использовал тест bpsw, т.е. сложность получилась nlogn. Такая штука отработала за 40 секунд.

При этом решето Эратосфена дает результат за 2.5 секунды.

А решету Аткина вообще меньше секунды требуется.
RASHFor
6 / 6 / 0
Регистрация: 12.02.2012
Сообщений: 224
08.07.2012, 14:20     Как выразить условие в операторе if для нахождения простого числа #44
Подскажите логику этого выражения :
C++
1
((n>2)?" 3":"")
Если n>2 истинна,то выводим 3,а если фальш то выводим- :
Так?

Добавлено через 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;
}
если n=1,то выводится 2.ошибка
b_kasenov47
14 / 14 / 1
Регистрация: 28.07.2012
Сообщений: 57
28.07.2012, 19:06     Как выразить условие в операторе if для нахождения простого числа #45
Эээ тут люди кажется не ту степь полезли))) Да ладно, coreshok, по поводу вашей находки (проверка делителей до н/2). Достаточно проверять число до корня, т.к все простые делители числа находятся в промежутке до корня. Ну вот соотетственно код:
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
#include <iostream>
#include <cstdio>
#include <cmath>
 
using namespace std;
 
bool is_prime(int n)
{
      if (n == 1)
           return false;
      int k = sqrt(n); // здесь компилятор выдаст предупреждение - не обращайте внимания на него
                           //если уж сильно бесит можно так 
                           // k = (int)(sqrt(double(n)));
      for (int i = 2; i <= k; i++)
           if (n % i == 0)
               return false;
       return true;
}
 
int main()
{
     int n;
     cout << "Vvedie chislo" << endl;
     cin >> n;
     if (is_prime(n))
     cout << "Chislo prostoe";
     else
     cout << "Chislo sostavnoe";
     return 0;
}
Thinker
28.07.2012, 19:42
  #46

Не по теме:

b_kasenov47, и ваш алгоритм в разы оптимизировать можно, получив при этом не вероятностный метод проверки, а точный метод

alsav22
5416 / 4812 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
29.07.2012, 09:26     Как выразить условие в операторе if для нахождения простого числа #47
Конкурс(поиск простых чисел)
Naz1kq
Сообщений: n/a
14.10.2013, 16:21     Как выразить условие в операторе if для нахождения простого числа #48
Здраствуйте раз уж тут много рпытных хотелось бы выложить свой вариант на критику..


C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<iostream>
using namespace std;
void main()
{
int count;
for(int easy=2; easy<=10000;easy++)
{
        for(int b=2; b < easy; b++)
        {   
        count = (easy%b);
        if(count == false)
            b=easy;
        }
            if(count != false)cout<<easy <<endl;
    
    }
    cin.get();
}
Thinker
Эксперт C++
4221 / 2195 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
14.10.2013, 19:13     Как выразить условие в операторе if для нахождения простого числа #49
Цитата Сообщение от Naz1kq Посмотреть сообщение
Здраствуйте раз уж тут много рпытных хотелось бы выложить свой вариант на критику..

Не по теме:

алгоритм уровня 5-го класса, вы уж не обессудьте...

BigT
Сообщений: n/a
26.06.2014, 23:48     Как выразить условие в операторе if для нахождения простого числа #50
Цитата Сообщение от coreshok Посмотреть сообщение
Господа, вот что мне нужно было.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
 
using namespace std;
 
int main()
{
    int i,j;
    bool isprime;
 
    for (i=1;i<100;i++)
    {
        isprime=true;
        for (j=2;j<=i/2;j++)
        if ((i%j)==0)
        isprime=false;
        if (isprime)
        cout <<i <<" is prime.\n";
    }
    return 0;
}
а если второй цикл for заключить в фигурные скобки, почему программа срабатывает некорректно. Выдает каждое простое число по множеству раз?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.09.2016, 15:38     Как выразить условие в операторе if для нахождения простого числа
Еще ссылки по теме:
функции для вычисления среднего значения и определения простого числа C++
C++ Создать функции для вычисления среднего значения и определения простого числа.
Составить программу для нахождения числа, которое образуется из данного натурального числа при записи его цифр в обратном порядке C++
C++ Программа для нахождения числа
C++ Макрос для нахождения наибольшего числа

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

Или воспользуйтесь поиском по форуму:
Pastuh
0 / 0 / 0
Регистрация: 29.08.2014
Сообщений: 1
09.09.2016, 15:38     Как выразить условие в операторе if для нахождения простого числа #51
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int s, n, c = 0, p = 1;
    cin >> n;
    for(int i = 0; i < n; i++)
        {
        cin >> s;
        if(s <= 1)  {cout << "Not prime" << endl; continue;}
        int g = sqrt(s);
        while(p!=g){
            if(s%p ==0) { c++;}
            p++;
            
            if (c > 1) {cout << "Not prime" << endl; break;}
            }
        if (c <= 1) cout << "Prime" << endl;
        
        c = 0; p = 1;
    }
Yandex
Объявления
09.09.2016, 15:38     Как выразить условие в операторе if для нахождения простого числа
Ответ Создать тему
Опции темы

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