Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

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

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

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

Приветствую вас!Уважаемые, подскажите пожалуйста как выразить условие в операторе if для нахождения простого числа, с помощью логических и операторов отношений.Если это возможно.Без массивов.Мне нужна просто маленькая подсказка, а остальное я хочу сам допетрить.В голове все знаю и понимаю как эти числа находятся, но не могу выразить в алгоритме кода .Язык С++.Заранее благодарен!
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.07.2012, 21:15
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Как выразить условие в операторе if для нахождения простого числа (C++):

Использование второй функции для нахождения простого числа и её ошибки - C++
Здравствуйте! Помогите разобраться с функциями, имеющие возвращающие значение. Суть программы в том, что она считывает число и...

Каково будет условие вывода на экран простого числа( оно делится только на 1 и на себя) - C++
Каково будет условие вывода на экран простого числа( оно делится только на 1 и на себя) Есть вот это(точно не знаю, верна ли она), она НЕ...

Условие в операторе switch - C++
Всем привет, есть коД: switch(TYPE) { case 1: total = number1 + number2; cout << "\n" <<...

Как выразить из числа Arc tg - C++
Подскажите пожалуйста. Как выразить из числа Arc tg из переменой zn в градусах!

Функция для простого числа - C++
В головной функции ввести массив чисел.И вывести количество простых чисел.Вот программа.Только почему-то, если она натыкается на составное...

как правильно в программке записать условие нахождения бесконечности? - C++
в примере y=exp(x)/x, где x принимает значения от -6 до + 1 c шагом 1 необходимо определить при каких x функция y=0 и бесконечности. ...

50
rinat_w
89 / 85 / 4
Регистрация: 13.11.2011
Сообщений: 192
Завершенные тесты: 1
06.07.2012, 17:47 #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;
}
2
coreshok
3 / 3 / 0
Регистрация: 23.12.2011
Сообщений: 55
06.07.2012, 18:12  [ТС] #32
Числа 2 и 3 тоже простые.
0
Catstail
Модератор
22904 / 11270 / 1832
Регистрация: 12.02.2012
Сообщений: 18,482
06.07.2012, 18:16 #33
Хочу сказать - идея использовать разложение 6k+1 - реальное алгоритмическое преимущество. С моей точки зрения это - действительно круто. rinat_w-молодец!
0
coreshok
3 / 3 / 0
Регистрация: 23.12.2011
Сообщений: 55
06.07.2012, 18:26  [ТС] #34
system("pause")- это что, функция с аргументом.Почему компилятор выдает ошибку что функция не за декларирована т.е.не объявлена.Если ее за комментировать, то все работает.
0
diagon
Higher
1932 / 1198 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
06.07.2012, 18:26 #35
Цитата Сообщение от Catstail Посмотреть сообщение
Хочу сказать - идея использовать разложение 6k+1 - реальное алгоритмическое преимущество.
С такой реализацией все равно квадратичная сложность получается, уменьшается только константа.
Хотя для очень больших чисел можно применять, если сделать нормальную проверку на простоту.

А я хотел бі разобраться с примером sooon`a . уменя какой то странный вывод:
Вы бы для начала посмотрели в main этого кода.
0
Catstail
Модератор
22904 / 11270 / 1832
Регистрация: 12.02.2012
Сообщений: 18,482
06.07.2012, 18:27 #36
Я в курсе... Но в 6 раз - тоже неплохо! Вот от этого я бы не стал отказываться, т.к. польза РЕАЛЬНА.
0
coreshok
3 / 3 / 0
Регистрация: 23.12.2011
Сообщений: 55
06.07.2012, 18:44  [ТС] #37
Ребята, что значит использовать разложение 6k+1?
0
Catstail
Модератор
22904 / 11270 / 1832
Регистрация: 12.02.2012
Сообщений: 18,482
06.07.2012, 18:46 #38
При просеивании чисел - брать только числа вида 6k+1 или 6k-1. Остальные проверять нет смысла - они точно не простые.
0
coreshok
3 / 3 / 0
Регистрация: 23.12.2011
Сообщений: 55
06.07.2012, 19:07  [ТС] #39
Благодарю! Это те условия которые описаны в операторах if в цикле for в главной функции.Интересный код.
0
PSIAlt
87 / 87 / 8
Регистрация: 19.06.2012
Сообщений: 245
06.07.2012, 21:43 #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;
}
1
rinat_w
89 / 85 / 4
Регистрация: 13.11.2011
Сообщений: 192
Завершенные тесты: 1
06.07.2012, 22:33 #41
PSIAlt, чето я немного не понял а где решето эратосфена?
0
PSIAlt
87 / 87 / 8
Регистрация: 19.06.2012
Сообщений: 245
06.07.2012, 23:00 #42
Ну любое не-простое число так или иначе делится на простое. Поэтому найденные простые числа мы складываем в primes и в дальнейшем при проверке на простость делим только на числа из этого списка. 2 и 3 не кладем т.к. эти числа не могут попасть в проверку by design
1
diagon
Higher
1932 / 1198 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
07.07.2012, 07:29 #43
Цитата Сообщение от PSIAlt Посмотреть сообщение
Предлагаю совместить с решетом эратосфена, улучшенный вариант=)
У вас тут нету решета Эратосфена, и это ни разу не улучшенный вариант.
Я сейчас попробовал запустить ваш код для n = 10^8, 3 минуты ждал результата, не дождался.

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

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

А решету Аткина вообще меньше секунды требуется.
0
RASHFor
6 / 6 / 0
Регистрация: 12.02.2012
Сообщений: 224
08.07.2012, 14:20 #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.ошибка
0
b_kasenov47
14 / 14 / 1
Регистрация: 28.07.2012
Сообщений: 57
28.07.2012, 19:06 #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;
}
0
28.07.2012, 19:06
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.07.2012, 19:06
Привет! Вот еще темы с ответами:

написать программу для прверки простого числа. язык программировние С - C++
Дано целое число, не превосходящее 2^32=4294967296. Написать программу для проверки того, является ли данное число простым. ...

функции для вычисления среднего значения и определения простого числа - C++
Здравствуйте. У меня просьба. Помогите выполнить задачу по программированию. Массив сформирован, есть код. А как дальше быть с...

Создать функции для вычисления среднего значения и определения простого числа. - C++
Из положительных значений двух целочисленных массивов различной размерно- сти сформировать общий массив. Найти среднее арифметическое...

Составить программу для нахождения числа, которое образуется из данного натурального числа при записи его цифр в обратном порядке - C++
помогите кто нибудь,пожалуйста,я на сайте первый раз,низнаю к кому обратиться..помогите написать прогу на языке с++ вот задание. ...


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

Или воспользуйтесь поиском по форуму:
45
Ответ Создать тему
Опции темы

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