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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 45, средняя оценка - 4.87
NaikoN
2 / 2 / 0
Регистрация: 01.05.2013
Сообщений: 109
02.05.2013, 11:41     Эффективный алгоритм поиска простых чисел на С++ #1
Хотел написать функцию которая вычисляет простое число или сложное, но оно не вычисляется. Цикл который я добавил в функцию не работает. Можете подсказать почему??? Заранее спасибо.
Простое число - которое делится на 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;
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
-=ЮрА=-
Заблокирован
Автор 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
Миниатюры
Эффективный алгоритм поиска простых чисел на С++  
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
03.05.2013, 13:14     Эффективный алгоритм поиска простых чисел на С++ #62
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
i <= num / 10 - у меня стоит в последней версии 100 я сейчас поставлю 256
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
i <= 32
магические числа.
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
достаточно прогонки до 128 для адекватной проверки
попробуйте прогнать тогда уж до 2 или даже до 1. Результаты будут еще круче.
вы же гоняете тесты только для чисел из моего файла, которые простые. там хоть сколько можно крутить цикл хоть до 128, хоть до 1, они будут простые в любом случае.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
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;
}
в олимпиадном программировании тест на простоту конкретного числа пишут именно так, и никто не парится по этому поводу...
-=ЮрА=-
Заблокирован
Автор 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
).
Миниатюры
Эффективный алгоритм поиска простых чисел на С++  
-=ЮрА=-
Заблокирован
Автор FAQ
03.05.2013, 13:45     Эффективный алгоритм поиска простых чисел на С++ #65
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
for(i = 9 + 2; i <= 1024 && bSimple; i += 2)
1E6 / 1E3 до sqrt видимо с этим педелом ниже никак.
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
03.05.2013, 13:52     Эффективный алгоритм поиска простых чисел на С++ #66
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
ксати ты даже тут слажал на счёт числа
ну да, перепутал последние 2 цифры, когда писал сообщение, что это меняет?
что насчет 128? снизьте его до 1 и покажите крутые результаты работы вашей программы
-=ЮрА=-
Заблокирован
Автор 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 тыс,

Не по теме:

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

ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
03.05.2013, 14:16     Эффективный алгоритм поиска простых чисел на С++ #68
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
это ведь этот код отстаиваешь
нет. с этими тестами я не знаком. я конкретно вашу программу критиковал за магические числа в основном цикле и следовательно за неадекватные значения OPCount.
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
- разобраться в чём?
c sqrt(n)
Taatshi
03.05.2013, 14:44
  #69
 Комментарий модератора 
Эмоции почистила. Есть желание продолжать - пожалуйста, в корректной форме.
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
03.05.2013, 15:52     Эффективный алгоритм поиска простых чисел на С++ #70
-=ЮрА=-, Напишите сюда ваш наиболее эффективный алгоритм. Простите меня за мою невнимательность, у меня не хватает времени, чтобы читать все ваши сообщения. Я хочу посмотреть на его правильность, может, даже, оценю его асимптотику. Может, я чего то не понимаю, а, может, вы сотворите чудо. Я надеюсь, что ваш последний алгоритм будет правильно выполнять поставленную задачу.
abit
 Аватар для abit
260 / 259 / 33
Регистрация: 03.02.2013
Сообщений: 709
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;
}
-=ЮрА=-
Заблокирован
Автор 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). Да среди нечётных будут попадаться составные и целесообразней было бы менять иногда и шаг, но в первом приближении просто хватит прогонки нечётных. В данный моент я прервусь и вернусь в тему через несколько часов, уже с кодом для сверхбольших чисел.
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
03.05.2013, 17:36     Эффективный алгоритм поиска простых чисел на С++ #73
-=ЮрА=-, напишите код, я его проверю на контесторе, я сомневаюсь в справедливости сказанного. В вашем рассуждении вы делаете ужасную ошибку, вы думаете, что через разряды, не зависимо от числа, можно проверять его на делимость....

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

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

если речь пошла о вероятностных алгоритмах - можно сейчас намутить обученную нечёткую нейронную сеть или генетический алгоритм и она будет давать ответ за несколько перемножений, не зависящих от N вообще, но естестно с определённой точностью гарантии
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 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)
Но этот алгоритм не полностью доказан, тк основывается на расширенной гипотезе Римана.
Но на всех обозримых числах он работает.
abit
 Аватар для abit
260 / 259 / 33
Регистрация: 03.02.2013
Сообщений: 709
03.05.2013, 18:11     Эффективный алгоритм поиска простых чисел на С++ #78
Ternsip,
я помню отрывочно этот алгоритм, и даже покопался в своей библотеке, ну например число 226801 или 486737 - не простые, а тест выдаёт простоту... а это даже не очень то и большие числа, понятно, что будет на больших интервалах

да просто взять из коллекции инета последовательности псевдопростых чисел - http://oeis.org/A163209 http://oeis.org/A001262 http://oeis.org/A020229
ваш метод на них не валится?
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
03.05.2013, 18:19     Эффективный алгоритм поиска простых чисел на С++ #79
abit, мой тест не выдал простоту, всё верно. нет, не валится.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.05.2013, 18:24     Эффективный алгоритм поиска простых чисел на С++
Еще ссылки по теме:

C++ функция поиска простых чисел
Алгоритм нахождения простых чисел C++
Алгоритм нахождения простых чисел C++

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

Или воспользуйтесь поиском по форуму:
abit
03.05.2013, 18:24     Эффективный алгоритм поиска простых чисел на С++
  #80

Не по теме:


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

Yandex
Объявления
03.05.2013, 18:24     Эффективный алгоритм поиска простых чисел на С++
Ответ Создать тему
Опции темы

Текущее время: 15:30. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru