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

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

Войти
Регистрация
Восстановить пароль
 
 
Thinker
Эксперт C++
4221 / 2195 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
#1

Быстрая проверка натурального числа на простоту - C++

29.09.2012, 21:35. Просмотров 45600. Ответов 90
Метки нет (Все метки)

Часто возникает задача проверки натурального числа на простоту. При этом имеются вероятностные и детерминированные методы проверки. Здесь рассматриваются только детерминированные алгоритмы, дающие 100% ответ на вопрос о простоте.

Хорошо известно такое утверждение: если натуральное число n>1 не делится ни на одно простое число, не превосходящее http://www.cyberforum.ru/cgi-bin/latex.cgi?\sqrt{n}, то оно простое. В связи с этим получается самый простой способ проверки на простоту алгоритм

C++
1
2
3
4
5
6
7
8
9
10
11
int Prime(unsigned long a)
{
   unsigned long i;
   if (a == 2)
      return 1;
   if (a == 0 || a == 1 || a % 2 == 0)
      return 0;
   for(i = 3; i*i <= a && a % i; i += 2)
      ;
   return i*i > a;
}
В данном алгоритме из множества http://www.cyberforum.ru/cgi-bin/latex.cgi?\{2,3,...,\sqrt{n}\} отброшено 50% четных чисел, так как если число a не делится на 2, то нет смыла делить его на 4, 6 и т.д. Данный метод можно усовершенствовать и отбросить из множества http://www.cyberforum.ru/cgi-bin/latex.cgi?\{2,3,...,\sqrt{n}\} больше чисел. Для этого выбирается некоторое число m, равное произведению простых чисел без степеней и рассматриваются только те элементы множества http://www.cyberforum.ru/cgi-bin/latex.cgi?\{2,3,...,\sqrt{n}\}, которые взаимно просты с m. Например, если m = 6 = 2*3, то из этого множества отбрасывается 66% элементов (ненужных проверок). В этом случае алгоритм будет быстрее предыдущего при больших n

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int Prime(unsigned long a)
{
   unsigned long i, j, bound;
   if (a == 0 || a == 1)
      return 0;
   if (a == 2 || a == 3 || a == 5)
      return 1;
   if (a%2 == 0 || a%3 == 0 || a%5 == 0)
      return 0;
   bound = sqrt((double)a);
   i = 7; j = 11;
   while (j <= bound && a%i && a%j)
   {
       i += 6; j += 6;
   }
   if (j <= bound || i <= bound && a%i == 0)
      return 0;
   return 1;
}
Если m = 30 = 2*3*5, то такой алгоритм будет еще быстрее и отбрасывает уже 74% лишних элементов

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
int Prime(unsigned long a)
{
   unsigned long i1, i2, i3, i4, i5, i6, i7, i8, bound;
   if (a == 0 || a == 1)
      return 0;
   if (a == 2 || a == 3 || a == 5 || a == 7 || a == 11 || a == 13 || a == 17 || a == 19 || a == 23 || a == 29)
      return 1;
   if (a%2 == 0 || a%3 == 0 || a%5 == 0 || a%7 == 0 || a%11 == 0 || a%13 == 0 || a%17 == 0 || a%19 == 0 || a%23 == 0 || a%29 == 0)
      return 0;
   bound = sqrt((double)a);
   i1 = 31; i2 = 37; i3 = 41; i4 = 43; i5 = 47; i6 = 49; i7 = 53; i8 = 59;
   while (i8 <= bound && a%i1 && a%i2 && a%i3 && a%i4 && a%i5 && a%i6 && a%i7 && a%i8)
   {
       i1 += 30; i2 += 30; i3 += 30; i4 += 30; i5 += 30; i6 += 30; i7 += 30; i8 += 30;
   }
   if (i8 <= bound ||
      i1 <= bound && a % i1 == 0 ||
      i2 <= bound && a % i2 == 0 ||
      i3 <= bound && a % i3 == 0 ||
      i4 <= bound && a % i4 == 0 ||
      i5 <= bound && a % i5 == 0 ||
      i6 <= bound && a % i6 == 0 ||
      i7 <= bound && a % i7 == 0)
         return 0;
   return 1;
}
Вот такие интересные наработки получились. У кого есть варианты, работающие быстрее, добавляйте.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.09.2012, 21:35     Быстрая проверка натурального числа на простоту
Посмотрите здесь:
C++ Проверка числа на простоту
C++ Проверка числа на простоту
C++ Проверка числа на простоту
C++ Проверка числа на простоту
C++ Проверка числа на простоту
C++ Проверка числа на простоту
Проверка числа на простоту C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
avovana
0 / 0 / 0
Регистрация: 08.09.2014
Сообщений: 84
29.10.2015, 11:37     Быстрая проверка натурального числа на простоту #81
C++
1
2
3
4
5
6
7
8
9
10
11
12
//------------Простое ли число?----------------------
bool isPrime(int number)
{
char buffer [50]="";
sprintf (buffer, "%d", number);
if (buffer [0] == '-')
return false;
if ( number == 0 || number == 1) return false;
int divisor;
for (divisor = number / 2; number%divisor != 0; --divisor);
return divisor == 1;
}
Krock21rus
74 / 74 / 19
Регистрация: 18.11.2013
Сообщений: 373
Завершенные тесты: 2
30.10.2015, 13:41     Быстрая проверка натурального числа на простоту #82
Интересно, слышал ли кто-нибудь про тест чисел на простоту за log(N)? BPSW называется
недоказанный, но проверенный на всех числах до 1e15

Добавлено через 3 минуты
http://e-maxx.ru/algo/bpsw
TFR104
0 / 0 / 0
Регистрация: 10.01.2017
Сообщений: 12
17.01.2017, 04:53     Быстрая проверка натурального числа на простоту #83
Как всегда сложно. Вот способ полегче
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
int main()
{
    const int N=50001;//Задаем размер выборки
    int arr[N];//Инициализируем массив для чисел 2 до N
    int k=0;
    int i;
    int bigResArr[N];//Результирующий массив для чисел больше 10
    int smallResArr[6];//Резальтирующий массив для чисел меньше 10
 
    //Цикл заполнения массива числами от 2 до N
    for(i=2; i<N; ++i){
        arr[k]=i;
        k++;
    }
 
    //Цикл для выполнения поиска и записавания простых чисел. Все операции привязаны к переменной k(номер элемента массивов)
    for(k=0; k<N; ++k)
    {
        if(arr[k]!=1 || arr[k]!=4 || arr[k]!=6 || arr[k]!=8 || arr[k]!=9)
        {
            //Условие заполнения результирующего массива простыми числами меньше 10
            if(arr[k]==2|| arr[k]==3 || arr[k]==5 || arr[k]==7)
            {
                smallResArr[k]=arr[k];
            }
            else
                {
            //Условие заполнения результирующего массива простыми числами большими чем 10
            if(arr[k]%2==0 || arr[k]%3==0 || arr[k]%5==0 || arr[k]%7==0)
                    {
                
                    }
            else
                        {
            bigResArr[k]= arr[k];
                        }       
                }
        }
    }
return 0;
}
ValeryS
Модератор
6537 / 5003 / 460
Регистрация: 14.02.2011
Сообщений: 16,639
17.01.2017, 05:14     Быстрая проверка натурального числа на простоту #84
Цитата Сообщение от TFR104 Посмотреть сообщение
//Условие заполнения результирующего массива простыми числами большими чем 10
if(arr[k]%2==0 || arr[k]%3==0 || arr[k]%5==0 || arr[k]%7==0)
число 121 простое?
не делится ни на 2, ни на 3, ни на 5, ни на 7
TheCalligrapher
С чаем беда...
Эксперт CЭксперт С++
3635 / 1910 / 503
Регистрация: 18.10.2014
Сообщений: 3,477
17.01.2017, 05:16     Быстрая проверка натурального числа на простоту #85
Цитата Сообщение от TFR104 Посмотреть сообщение
Вот способ полегче
И что это вообще за чудо креативного программирования? Что, по-вашему, делает этот код? Числа 121, 143, 187 и т.д. смело отправляются в bigResArr, что, как мой умище мне подсказывает, означает, что они простые, так?
Croessmah
Модератор
Эксперт CЭксперт С++
12979 / 7291 / 812
Регистрация: 27.09.2012
Сообщений: 18,007
Записей в блоге: 3
Завершенные тесты: 1
17.01.2017, 05:49     Быстрая проверка натурального числа на простоту #86
Цитата Сообщение от TFR104 Посмотреть сообщение
Вот способ полегче
Вот еще легче:
C++
1
2
3
4
5
6
7
8
#include <iostream>
 
int main()
{
   int x = 10;
   std::cin >> x;
   std::cout << ((x&1)?"prostoe, sto pudov":"ne prostoe") << std::endl;
}
TFR104
0 / 0 / 0
Регистрация: 10.01.2017
Сообщений: 12
17.01.2017, 05:51     Быстрая проверка натурального числа на простоту #87
Действительно. Ну так вы же модератор. Удалите сообщения.
PetrSergeev
0 / 0 / 0
Регистрация: 06.04.2017
Сообщений: 2
06.04.2017, 22:25     Быстрая проверка натурального числа на простоту #88
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
//программа поиска простых чисел методом перебора делителей
#include<iostream>
#include <ctime>
using namespace std;
 
 
int main() 
{
    long max =1000000;//диапазон поиска от 1 до мах
    int n(0);//счетчик найденных простых чисел
    int s;
    clock_t timer;
    timer = clock();//время начала поиска
    cout << "Simple numbers: 0>>>"<<max<<endl;
    
    for ( int i = 1; i < max; i+=2)//проверяем все нечетные числа
    {
        s=0;//обнуляем счетчик делителей
        for (int j = 3; j <= i/j; j++) {
            //находим остаток от деления числа i на j 
            if (i % j == 0) {
                s++;//если остаток от деления равно 0, то j является делителем числа i, увеличиваем счетчик делителей на 1
                break;//проверяем следующее число
            }
        }
        if (s == 0) {  n++; }//простое число равно значению i при желании можно распечатать на экран, но снижает скорость
        
    }
    timer = clock()-timer ;//вычисляем время потраченное на поиск
    cout << "\n\aend:" << float(timer)/CLOCKS_PER_SEC<<"s"<<endl;
    cout << "find " << n << " numbers.\n";
    system("pause");
    return 0;
}
ValeryS
Модератор
6537 / 5003 / 460
Регистрация: 14.02.2011
Сообщений: 16,639
06.04.2017, 22:48     Быстрая проверка натурального числа на простоту #89
Цитата Сообщение от PetrSergeev Посмотреть сообщение
long max =1000000;//диапазон поиска от 1 до мах
маловато чтото за миллион тут бы т разговора не было
Цитата Сообщение от PetrSergeev Посмотреть сообщение
//проверяем все нечетные числа
а четные куда дел? число 2 простое
PetrSergeev
0 / 0 / 0
Регистрация: 06.04.2017
Сообщений: 2
07.04.2017, 09:33     Быстрая проверка натурального числа на простоту #90
Цитата Сообщение от ValeryS Посмотреть сообщение
маловато чтото за миллион тут бы т разговора не было
а четные куда дел? число 2 простое
2 - простое, но оно известно, просто распечатать надо в самом начале. Дальше вроде все правильно находит.... можно приспособить для проверки одного числа или поиска в диапазоне от min до max. 10млн у меня перебирает за 20 с, 1 млн меньше 1с.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.04.2017, 23:48     Быстрая проверка натурального числа на простоту
Еще ссылки по теме:
Проверка на простоту числа C++
Проверка числа на простоту (нужны комментарии) C++
C++ Проверка на простоту числа - исправить ошибки в коде
C++ Робота с динамической памятью, проверка числа на простоту
Проверка цифр натурального числа C++

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

Или воспользуйтесь поиском по форуму:
Байт
Эксперт C
15635 / 9977 / 1499
Регистрация: 24.12.2010
Сообщений: 18,735
08.04.2017, 23:48     Быстрая проверка натурального числа на простоту #91
ValeryS, Имхо, этот форум для того и создан, чтобы люди совершенно разной квалификации предлагали решения как простых, так и сложных задач. И понимали бы суть задачи так, как она им видится. И предлагали бы временами свои, вполне симпатичные, решения

Добавлено через 2 минуты
Цитата Сообщение от PetrSergeev Посмотреть сообщение
10млн у меня перебирает за 20 с, 1 млн меньше 1с.
Это очень плохой результат даже для маломощных компьютеров типа 1 ГигаФлоп. Твой алгоритм делает чудовищное количество лишних проверок.
Yandex
Объявления
08.04.2017, 23:48     Быстрая проверка натурального числа на простоту
Ответ Создать тему
Опции темы

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