Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 45, средняя оценка - 4.87
NaikoN
2 / 2 / 1
Регистрация: 01.05.2013
Сообщений: 109
#1

Эффективный алгоритм поиска простых чисел на С++ - C++

02.05.2013, 11:41. Просмотров 6708. Ответов 94
Метки нет (Все метки)

Хотел написать функцию которая вычисляет простое число или сложное, но оно не вычисляется. Цикл который я добавил в функцию не работает. Можете подсказать почему??? Заранее спасибо.
Простое число - которое делится на 1 и на само себя, сложное число-которое делится на 1 и на само себя и на какое-то еще число, 5 -простое число, 10-сложное число.
P.S. Вот программа:
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
#include<iostream>
#include<fstream>
#include<math.h>
using namespace std;
 int simple (int x,int i=1)
{
    int fn;
    for(i=1;i<=x;i++)
    {
        if(i!=1||i!=x)
        {
            if(!(x%i))
            {
                fn=0;
                return fn;
            }
        }
    }
    fn=1;
    return fn;
}
int main()
{
    //ifstream cin("input.txt");
    long int x,i=1;
    cin>>x;
    if(simple(x,i)==0)
    {
        cout<<"composite";
        return 0;
    }
    if(simple(x,i)==1)
    {
        cout<<"prime";
            return 0;
    }
    return 0;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.05.2013, 11:41
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Эффективный алгоритм поиска простых чисел на С++ (C++):

Алгоритм поиска простых чисел
Доброго времени суток. Помогите пожалуйста с алгоритмом поиска простых чисел в...

Эффективный алгоритм для поиска минимума в массиве
В массиве X(N) найти значения двух наименьших элементов и вывести их в порядке...

функция поиска простых чисел
не могу сделать функции для поиска простых чисел, вот код функции int...

Программа поиска простых чисел
Необходимо написать программу для поиска простых чесил в интервале от 1 до 100...

Функция для поиска ближайших простых чисел
Ув. товарищи программисты , нужна помощь. Требуется функция с помощью которой...

Почему программа поиска простых чисел работает только до 61?
Добрый день, Помогите, пожалуйста, разобраться. Программа для поиска простых...

94
-=ЮрА=-
Заблокирован
Автор FAQ
03.05.2013, 13:08 #61
Цитата Сообщение от Ternsip Посмотреть сообщение
-=ЮрА=-, ваша программа всё ещё не работает 12312449 число не простое делитель 47
- ещё раз поставишь число с пределом выше INT_MAX в алгоритм где идёт int и long - пеняй на себя, два раза предупреждать не буду. Ты лучше автору темы скажи что до последнего кода у тебя шла полная лажа даже на числах меньших 50000


На исследуй
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
#include <cmath>
#include <fstream>
#include <iostream>
using namespace std;
 
bool isSimple(long long num);
double OPCount = 0;
 
int main()
{
    long num     = 0;
    if(isSimple(12312449))
        cout<<num<<" SIMPLE ";
    else
        cout<<num<<" NOT SIMPLE ";
    return 0;
}
 
bool isSimple(long long num)
{
    long long i  = 0;
    bool bSimple = true;
    if( num < 0 )
        num *= -1;
    OPCount += 1;
    for(i = 2; i <= 9 && bSimple; i++)
    {
        OPCount += 1;
        if( i != num )
            bSimple = num % i != 0;
    }
    for(i = 9 + 2; i <= 256 && bSimple; i += 2)
    {
        if( i != num )
            bSimple = num % i != 0;
        if(!bSimple)
            cout<<"DIVIDER : "<<i<<endl;
        OPCount += 1;
    } 
    return bSimple;
}
http://ideone.com/CkEUko
1
Миниатюры
Эффективный алгоритм поиска простых чисел на С++  
ya_noob
_
314 / 148 / 27
Регистрация: 08.10.2011
Сообщений: 432
03.05.2013, 13:14 #62
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
i <= num / 10 - у меня стоит в последней версии 100 я сейчас поставлю 256
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
i <= 32
магические числа.
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
достаточно прогонки до 128 для адекватной проверки
попробуйте прогнать тогда уж до 2 или даже до 1. Результаты будут еще круче.
вы же гоняете тесты только для чисел из моего файла, которые простые. там хоть сколько можно крутить цикл хоть до 128, хоть до 1, они будут простые в любом случае.
0
salam
174 / 155 / 28
Регистрация: 10.07.2012
Сообщений: 766
03.05.2013, 13:20 #63
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 int simple (int x,int i=1) // не стоит делать по умолчанию параметр i: просто бессмысленно.
{
    int fn;
    for(i=1;i<=x;i++) // если вы хотите отсечь проверку на делимость для 1 и х, логично цикл сделать
    {                     // не в пределе [1; x], а [2; x-1]
        if(i!=1||i!=x)  // не нужно, стало быть
        {
            if(!(x%i))
            {
                fn=0;
                return fn;
            }
        }
    }
    fn=1;
    return fn;
}
вообще ваш алгоритм не эффективен с точки зрения сложности. искать делители разумно на отрезке [2; sqrt(N)].
то есть как-то так:

C++
1
2
3
4
5
6
bool _isprime(int n) {
   for(int i=2; i*i <= n; i++)
      if(n % i == 0)
         return false;
   return true;
}
в олимпиадном программировании тест на простоту конкретного числа пишут именно так, и никто не парится по этому поводу...
0
-=ЮрА=-
Заблокирован
Автор FAQ
03.05.2013, 13:43 #64
Цитата Сообщение от salam Посмотреть сообщение
bool _isprime(int n) {
* *for(int i=2; i*i <= n; i++)
* * * if(n % i == 0)
* * * * *return false;
* *return true;
}
- ужас

Цитата Сообщение от ya_noob Посмотреть сообщение
если вы за такие исследования еще и просить деньги будете, то вам дадут не пару К зеленых, а 1 фиолетовый под глазом.
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
#include <cmath>
#include <fstream>
#include <iostream>
using namespace std;
 
bool isSimple(long num);
double OPCount = 0;
 
int main()
{
    long num     = 0;
    long nCount  = 0;
    ofstream ofs("check.txt");
    for(num = 2; num < 999984; num++)
    {
        if(isSimple(num))
        {
            cout<<"\r"<<num;
            ofs<<num<<endl;
            nCount++;
            cout<<" ITERS : "<<OPCount
                <<" COUNT : "<<nCount;
        }
        //else
        //{
        //  cout<<"\r"<<num<<" NOT SIMPLE ";
        //  ofs<<num<<" NOT SIMPLE "<<endl;
        //  system("pause");
        //}
    
    //    else
      //      continue;
        //if( nCount && nCount % 80 == 0 )
          //  system("pause");
    }
    ofs.close();
    cout<<endl;
    system("pause");
    return 0;
}
 
bool isSimple(long num)
{
    long i  = 0;
    bool bSimple = true;
    if( num < 0 )
        num *= -1;
    OPCount += 1;
    for(i = 2; i <= 9 && bSimple; i++)
    {
        OPCount += 1;
        if( i != num )
            bSimple = num % i != 0;
    }
    for(i = 9 + 2; i <= 1024 && bSimple; i += 2)
    {
        if( i != num )
            bSimple = num % i != 0;
    //  if(!bSimple)
    //      cout<<"DIVIDER : "<<i<<endl;
        OPCount += 1;
    } 
    return bSimple;
}
В каталоге появится check.txt в котором как и в primes будет ровно 78498 значений (ксати ты даже тут слажал на счёт числа (скрин видно)
Цитата Сообщение от ya_noob Посмотреть сообщение
Вот список простых чисел до миллиона (78489 штук): primes.zip
).
1
Миниатюры
Эффективный алгоритм поиска простых чисел на С++  
-=ЮрА=-
Заблокирован
Автор FAQ
03.05.2013, 13:45 #65
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
for(i = 9 + 2; i <= 1024 && bSimple; i += 2)
1E6 / 1E3 до sqrt видимо с этим педелом ниже никак.
0
ya_noob
_
314 / 148 / 27
Регистрация: 08.10.2011
Сообщений: 432
03.05.2013, 13:52 #66
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
ксати ты даже тут слажал на счёт числа
ну да, перепутал последние 2 цифры, когда писал сообщение, что это меняет?
что насчет 128? снизьте его до 1 и покажите крутые результаты работы вашей программы
0
-=ЮрА=-
Заблокирован
Автор FAQ
03.05.2013, 14:10 #67
Цитата Сообщение от ya_noob Посмотреть сообщение
снизьте его до 1 и покажите крутые результаты работы вашей программы
- хорошо тогда пусть до единицы будет снижено здесь
Цитата Сообщение от Ternsip Посмотреть сообщение
cout << MillerRabin(n, 19);
, это ведь этот код отстаиваешь


Цитата Сообщение от ya_noob Посмотреть сообщение
попробуйте прогнать тогда уж до 2 или даже до 1. Результаты будут еще круче.
вы же гоняете тесты только для чисел из моего файла, которые простые. там хоть сколько можно крутить цикл хоть до 128, хоть до 1, они будут простые в любом случае.
прогнал код поста 67 на числах до 2-х млн
1999993 ITERS : 1.02664e+008 COUNT : 152182
Для продолжения нажмите любую клавишу . . .
Напомню у тебя с твоим другом (а может и клоном твоим) было 10^9 на значении 400 тыс,

Не по теме:

Да я написал админу + прошу проверить пользователей в данной теме на клонированность уж очень подозрительны некоторые включения ответчиков.

0
ya_noob
_
314 / 148 / 27
Регистрация: 08.10.2011
Сообщений: 432
03.05.2013, 14:16 #68
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
это ведь этот код отстаиваешь
нет. с этими тестами я не знаком. я конкретно вашу программу критиковал за магические числа в основном цикле и следовательно за неадекватные значения OPCount.
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
- разобраться в чём?
c sqrt(n)
0
Taatshi
03.05.2013, 14:44
  #69
 Комментарий модератора 
Эмоции почистила. Есть желание продолжать - пожалуйста, в корректной форме.
0
Ternsip
663 / 191 / 29
Регистрация: 10.05.2012
Сообщений: 595
03.05.2013, 15:52 #70
-=ЮрА=-, Напишите сюда ваш наиболее эффективный алгоритм. Простите меня за мою невнимательность, у меня не хватает времени, чтобы читать все ваши сообщения. Я хочу посмотреть на его правильность, может, даже, оценю его асимптотику. Может, я чего то не понимаю, а, может, вы сотворите чудо. Я надеюсь, что ваш последний алгоритм будет правильно выполнять поставленную задачу.
0
abit
272 / 271 / 83
Регистрация: 03.02.2013
Сообщений: 770
03.05.2013, 16:00 #71
Ternsip,
этот известный метод достаточно эффективен?
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
#include <iostream>
#include <cmath>
#include <fstream>
 
using namespace std;
 
int main ()
{
 int limit = 1000;
 int root = (int)ceil(sqrt(limit));
 bool sieve[limit];
 int primes[(limit/2)+1];
 int insert = 2;
 primes[0] = 2;
 primes[1] = 3;
 for (int z = 0; z < limit; z++) sieve[z] = false; 
 for (int x = 1; x <= root; x++)
 {
 for (int y = 1; y <= root; y++)
 {
 int n = (4*x*x)+(y*y);
 if (n <= limit && (n % 12 == 1 || n % 12 == 5)) sieve[n] ^= true;
 n = (3*x*x)+(y*y);
 if (n <= limit && n % 12 == 7) sieve[n] ^= true;
 n = (3*x*x)-(y*y);
 if (x > y && n <= limit && n % 12 == 11) sieve[n] ^= true;
 }
 }
 for (int r = 5; r <= root; r++) if (sieve[r]) for (int i = r*r; i < limit; i += r*r) sieve[i] = false;
 for (int a = 5; a < limit; a++)
 {
 if (sieve[a])
 {
 primes[insert] = a;
 insert++;
 }
 }
 ofstream file;
 char filename[100];
 sprintf(filename, "output.txt", limit);
 file.open(filename);
 for (int a = 0; a < insert; a++) file << primes[a] << ((a == insert-1) ? "" : "\n");
 file.close();
 return 0;
}
0
-=ЮрА=-
Заблокирован
Автор FAQ
03.05.2013, 16:58 #72
Цитата Сообщение от Ternsip Посмотреть сообщение
-=ЮрА=-, Напишите сюда ваш наиболее эффективный алгоритм. Простите меня за мою невнимательность, у меня не хватает времени, чтобы читать все ваши сообщения. Я хочу посмотреть на его правильность, может, даже, оценю его асимптотику. Может, я чего то не понимаю, а, может, вы сотворите чудо. Я надеюсь, что ваш последний алгоритм будет правильно выполнять поставленную задачу.
- очень конструктивно!Хорошо сначала теоретическое обоснование
Пусть с = 1EN причём a*b = c, тогда порядки делителей составят
http://www.cyberforum.ru/cgi-bin/latex.cgi?\begin{matrix} <br />
a   &  b  \\  <br />
k   & 1EN \\  <br />
10*k & 1EN /(10*k)  = 1EN - 1\\  <br />
100*k & 1EN /(100*k) = 1EN - 2  \\ <br />
 .... & \\  <br />
k*E(N/2) & 1EN /[k*E(N/2)] = 1E(N/2)<br />
 \end{matrix}
далее а и b поменяются местами т.е если мы хотим посмотреть делители числа достаточно пройтись по половине разрядов. При этом следует отметить что львиная доля составных чисел будут иметь делители уже на промежутке 1...9 а вот все оставшиеся будут совокупностью двух простых чисел. Т.е задача стоит в прогонке делителей числа от 1 до sqrt(N), причём нам вначале достаточно прогнать первый десяток чисел, а затем лишь смотреть нечётные числа (т.е шаг 2). Да среди нечётных будут попадаться составные и целесообразней было бы менять иногда и шаг, но в первом приближении просто хватит прогонки нечётных. В данный моент я прервусь и вернусь в тему через несколько часов, уже с кодом для сверхбольших чисел.
0
Ternsip
663 / 191 / 29
Регистрация: 10.05.2012
Сообщений: 595
03.05.2013, 17:36 #73
-=ЮрА=-, напишите код, я его проверю на контесторе, я сомневаюсь в справедливости сказанного. В вашем рассуждении вы делаете ужасную ошибку, вы думаете, что через разряды, не зависимо от числа, можно проверять его на делимость....

Добавлено через 7 минут
abit, 1) это решето, а не проверка одного числа на простоту 2) мы договорились не пользоваться решетом и прекальком 3) если я попрошу вас проверить число ~10^20, которое будет простым заведомо, сколько памяти и времени потребуется...

Добавлено через 5 минут
-=ЮрА=-, для абсолютного теста я возьму несколько больших чисел (около 10 шт) и просумирую время выполнения вашего и моего алгоритма на них, в случае, если вы сможете написать код, который работает правильно
0
abit
272 / 271 / 83
Регистрация: 03.02.2013
Сообщений: 770
03.05.2013, 17:44 #74
Ternsip,
1) это решето, а не проверка одного числа на простоту 2) мы договорились не пользоваться решетом и прекальком 3) если я попрошу вас проверить число ~10^20, которое будет простым заведомо, сколько памяти и времени потребуется...
извиняюсь я не читал все страницы темы и о чём вы договаривались...
обычно числа типа 10^20 никто не проверяет на простоту, есть эффективные методы генерации простых чисел для нужд криптографии
на вскидку если без решета - я бы проверил что число >10, а затем что последняя цифра в числе - 1,3,7 или 9, потом уже искал бы делители методом перебора от 1 до sqrt(N) (N-исходное число) исключая все чётные и кратные 5
это вроде бы уже не решето? насколько это эффективно в таком виде? впринципе и то решето можно свести к подобному подходу
0
Ternsip
663 / 191 / 29
Регистрация: 10.05.2012
Сообщений: 595
03.05.2013, 17:55 #75
abit, ну в итоге ваш алгоритм O(sqrt(N)/10) = O(sqrt(N)) по свойствам О-большое, а алгоритм Миллера Рабина O (log^3(N)), сравните эти 2 функции
0
abit
272 / 271 / 83
Регистрация: 03.02.2013
Сообщений: 770
03.05.2013, 18:00 #76
Цитата Сообщение от Ternsip Посмотреть сообщение
abit, ну в итоге ваш алгоритм O(sqrt(N)/10) = O(sqrt(N)) по свойствам О-большое, а алгоритм Миллера Рабина O (log^3(N)), сравните эти 2 функции
без спора, мне не тягаться с алгоритмами двух умных мужиков в своей наивности и простоте, но немного подумав - этот алгоритм не гарантирует правильный ответ, а мой гарантирует

если речь пошла о вероятностных алгоритмах - можно сейчас намутить обученную нечёткую нейронную сеть или генетический алгоритм и она будет давать ответ за несколько перемножений, не зависящих от N вообще, но естестно с определённой точностью гарантии
0
Ternsip
663 / 191 / 29
Регистрация: 10.05.2012
Сообщений: 595
03.05.2013, 18:04 #77
abit, вы плохо знаете тест, если взять число 2 * log(N) ^ 2 как точность, то ошибки никогда не произойдёт
http://ru.wikipedia.org/wiki/%D0%A2%...81%D0%B5%D0%BB)
Но этот алгоритм не полностью доказан, тк основывается на расширенной гипотезе Римана.
Но на всех обозримых числах он работает.
0
abit
272 / 271 / 83
Регистрация: 03.02.2013
Сообщений: 770
03.05.2013, 18:11 #78
Ternsip,
я помню отрывочно этот алгоритм, и даже покопался в своей библотеке, ну например число 226801 или 486737 - не простые, а тест выдаёт простоту... а это даже не очень то и большие числа, понятно, что будет на больших интервалах

да просто взять из коллекции инета последовательности псевдопростых чисел - http://oeis.org/A163209 http://oeis.org/A001262 http://oeis.org/A020229
ваш метод на них не валится?
0
Ternsip
663 / 191 / 29
Регистрация: 10.05.2012
Сообщений: 595
03.05.2013, 18:19 #79
abit, мой тест не выдал простоту, всё верно. нет, не валится.
0
abit
03.05.2013, 18:24     Эффективный алгоритм поиска простых чисел на С++
  #80

Не по теме:


Ternsip,
так дайте его в студию) или я что-то пропустил? хочется проверить самому, чисто академический интерес
хотя что он не валится - я допускаю, у нас видимо какой-то урезанный был, по инету всё намного сложнее, чем у меня

0
03.05.2013, 18:24
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.05.2013, 18:24
Привет! Вот еще темы с ответами:

Алгоритм нахождения простых чисел
Не так давно начал изучать с++. Вот попытался написать программу которая...

Алгоритм нахождения простых чисел
Не могу найти в интернете нормальный код алгоритма нахождения простых чисел....

Алгоритм нахождения простых чисел
Вопросы: 1) Нужен алгоритм проверки числа (является ли число простим). Нужно...

Алгоритм отбора простых чисел
Сижу учу С++ по Шилтду (Базовый курс) И вот папался такой алгоритм, на...


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

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

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