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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 45, средняя оценка - 4.87
NaikoN
2 / 2 / 0
Регистрация: 01.05.2013
Сообщений: 109
#1

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

02.05.2013, 11:41. Просмотров 6399. Ответов 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++):

функция поиска простых чисел - C++
не могу сделать функции для поиска простых чисел, вот код функции int prost(int x) { if (x/2) return true; else ...

Программа поиска простых чисел - C++
Необходимо написать программу для поиска простых чесил в интервале от 1 до 100 на языке СИ.Простое число — это натуральное число, имеющее...

Функция для поиска ближайших простых чисел - C++
Ув. товарищи программисты , нужна помощь. Требуется функция с помощью которой можно найти 2 ближайших ПРОСТЫХ числа к веденному числу. ...

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

Алгоритм нахождения простых чисел - C++
Не могу найти в интернете нормальный код алгоритма нахождения простых чисел. Помогите пожалуйста. Добавлено через 2 минуты ...

Алгоритм нахождения простых чисел - C++
Вопросы: 1) Нужен алгоритм проверки числа (является ли число простим). Нужно чтобы алгоритм был быстрым (нужно проделать 104 операций за...

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
_
313 / 147 / 9
Регистрация: 08.10.2011
Сообщений: 432
03.05.2013, 13:14 #62
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
i <= num / 10 - у меня стоит в последней версии 100 я сейчас поставлю 256
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
i <= 32
магические числа.
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
достаточно прогонки до 128 для адекватной проверки
попробуйте прогнать тогда уж до 2 или даже до 1. Результаты будут еще круче.
вы же гоняете тесты только для чисел из моего файла, которые простые. там хоть сколько можно крутить цикл хоть до 128, хоть до 1, они будут простые в любом случае.
0
salam
171 / 152 / 16
Регистрация: 10.07.2012
Сообщений: 751
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
_
313 / 147 / 9
Регистрация: 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
_
313 / 147 / 9
Регистрация: 08.10.2011
Сообщений: 432
03.05.2013, 14:16 #68
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
это ведь этот код отстаиваешь
нет. с этими тестами я не знаком. я конкретно вашу программу критиковал за магические числа в основном цикле и следовательно за неадекватные значения OPCount.
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
- разобраться в чём?
c sqrt(n)
0
Taatshi
03.05.2013, 14:44
  #69
 Комментарий модератора 
Эмоции почистила. Есть желание продолжать - пожалуйста, в корректной форме.
0
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
03.05.2013, 15:52 #70
-=ЮрА=-, Напишите сюда ваш наиболее эффективный алгоритм. Простите меня за мою невнимательность, у меня не хватает времени, чтобы читать все ваши сообщения. Я хочу посмотреть на его правильность, может, даже, оценю его асимптотику. Может, я чего то не понимаю, а, может, вы сотворите чудо. Я надеюсь, что ваш последний алгоритм будет правильно выполнять поставленную задачу.
0
abit
271 / 270 / 35
Регистрация: 03.02.2013
Сообщений: 761
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
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
03.05.2013, 17:36 #73
-=ЮрА=-, напишите код, я его проверю на контесторе, я сомневаюсь в справедливости сказанного. В вашем рассуждении вы делаете ужасную ошибку, вы думаете, что через разряды, не зависимо от числа, можно проверять его на делимость....

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

Добавлено через 5 минут
-=ЮрА=-, для абсолютного теста я возьму несколько больших чисел (около 10 шт) и просумирую время выполнения вашего и моего алгоритма на них, в случае, если вы сможете написать код, который работает правильно
0
abit
271 / 270 / 35
Регистрация: 03.02.2013
Сообщений: 761
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
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 функции
0
03.05.2013, 17:55
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.05.2013, 17:55
Привет! Вот еще темы с ответами:

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

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

Алгоритм нахождения ПРОСТЫХ чисел в файле - C++
Заполнить файл f целыми числами, полученными с помощью генератора случайных чисел. Из файла f получить файл g, оставив только ПРОСТЫЕ...

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


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

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

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