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

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

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

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

29.09.2012, 21:35. Просмотров 46975. Ответов 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;
}
Вот такие интересные наработки получились. У кого есть варианты, работающие быстрее, добавляйте.
28
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.09.2012, 21:35
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Быстрая проверка натурального числа на простоту (C++):

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

Проверка числа на простоту - C++
Помогите решить 2 задачки, пожалуйста, 1. Написать программу для проверки натурального числа N на простоту. N вводится с клавиатуры. ...

Проверка числа на простоту - C++
Дано натуральное число n&gt;1. Проверьте, является ли оно простым. Программа должна вывести слово YES, если число простое и NO, если число...

Проверка на простоту числа - C++
как мне сделать так, чтобы узнать простое является число или составное, не через bool, а как-нибудь через оператор switch case: т е, case...

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

Проверка числа на простоту - C++
Почему, если необ. проверить, является ли число простым(напр. ч-ло n),можно просматривать делители не от 2 до n, а от 2 до sqrt(n)? P.S....

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Thinker
Эксперт C++
4226 / 2200 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
30.10.2012, 20:58  [ТС] #31
AEXks, если зафиксировать модуль m, то в этом случае сложность алгоритма будет http://www.cyberforum.ru/cgi-bin/latex.cgi?O(\sqrt{n}), где n - исследуемое число. Поэтому есть ли смысл идти в этом направлении. Вы же прекрасно понимаете, что в ассимметричных шифрах используются ОЧЕНЬ большие числа, а если речь об эллиптических кривых, то там совсем принцип другой. Изначально моя цель была, действительно, улучшить широко используемый алгоритм проверки на простоту, но при общих равных условиях (при активном одном ядре), третий алгоритм из первого поста получился самым удачным. Другие алгоритмы, которые я здесь не выкладывал, уступают относительно (условной) сложности реализации и скорости. Да, при больших числах скорость медленно начинает расти относительного третьего алгоритма, но сложность остается http://www.cyberforum.ru/cgi-bin/latex.cgi?O(\sqrt{n}), поэтому я эту затею бросил.
0
AEXks
24 / 3 / 1
Регистрация: 28.10.2012
Сообщений: 35
30.10.2012, 21:01 #32
Thinker, а есть ли другие точные алгоритмы при меньшей сложности? так как скорость просчета на _int64 быстр, то нужно как то попробовать реализовать деление по модулю двух _int64 , _int64 на максимум _int64 . Я уже написал мысли по этому поводу.. там нужны битовые операции, а именно я не знаю есть ли функции вычисляющие номер самого старшего значимого бита.
0
Thinker
Эксперт C++
4226 / 2200 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
30.10.2012, 21:08  [ТС] #33
Тот же AKS, но им не интересовался. Мне интересно было применить некоторые познания из теории чисел на практике и, отчасти, это сделать удалось. Ваша идея с GPU очень интересна, но не понятно как Вы это реализовали.
0
AEXks
24 / 3 / 1
Регистрация: 28.10.2012
Сообщений: 35
30.10.2012, 21:25 #34
Thinker, в каком плане не понятно ? могу выложить код функции обработчика и ядра =) обсудим
0
Thinker
Эксперт C++
4226 / 2200 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
30.10.2012, 21:30  [ТС] #35
Цитата Сообщение от AEXks Посмотреть сообщение
Thinker, в каком плане не понятно ?

Не по теме:

я просто не работал программно с GPU

0
AEXks
24 / 3 / 1
Регистрация: 28.10.2012
Сообщений: 35
30.10.2012, 21:38 #36
Тут все просто: так как мы выкинули 2ки и 3ки то зачем нам их проверять? из-за этого получается две последовательности чисел, которую мы и задаем. на GPU мы имеем много нитей, которые выполняют "свой" код. По этому мы берем и выполняем параллельно проверку сразу нескольких делителей. Этот код заточен на проверку сразу массива чисел, но я тут проверял всегда одно =)

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
__global__ void is_simple(ulong *arr, ulong *info, int idx, ulong sqr, ulong shift, ulong count)
{
    int thIdx = blockIdx.x * blockDim.x + threadIdx.x;
    ulong x;
    
    if(thIdx % 2 == 0)
        x = 3 * thIdx + 5;
    else
        x = 3 * (thIdx - 1) + 7;
    
    ulong temp = arr[idx];
    ulong rez = 1;
    
    for(ulong i = 0; i < count; ++i)
    {       
        rez = rez xor ((temp % x) == 0);
        x += shift; 
    }
    info[thIdx] = rez;
}
 
void is_simple_arr(ulong *in_arr,ulong *out_arr, int dim_arr, float *time)
{
    dim3 blocks(60000);
    dim3 threads(256);
    int coef = 3;
    ulong *devArr,*devInfo;
    cudaEvent_t start,stop;
    
    cudaEventCreate(&start);
    cudaEventCreate(&stop); 
    
    cudaMalloc((void**)&devArr, dim_arr * sizeof(ulong));
    cudaMalloc((void**)&devInfo, blocks.x * threads.x * sizeof(ulong));
    
    device_ptr<ulong> for_reduction(devInfo);
    cudaMemcpy(devArr, in_arr, dim_arr * sizeof(ulong), cudaMemcpyHostToDevice);
    ulong red_rez;
    
    cudaEventRecord(start, 0); 
    for(int i = 0; i < dim_arr; ++i)
    {
        ulong sq = sqrt(in_arr[i]) + 1;
        if(in_arr[i] % 2 != 0 && in_arr[i] % 3 != 0)
        {
            is_simple<<< blocks, threads >>>(devArr, devInfo, i, sq, blocks.x * threads.x * coef, sq/(blocks.x * threads.x * coef) + 1);
            red_rez = reduce(for_reduction, for_reduction + blocks.x * threads.x,999,thrust::minimum<ulong>());
            out_arr[i] = red_rez;           
        }
        else
        {
            out_arr[i] = 0;
        }
    }
    
    cudaEventRecord(stop, 0);
    cudaEventSynchronize(stop);
    cudaEventElapsedTime(time,start, stop);
}
0
Thinker
Эксперт C++
4226 / 2200 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
30.10.2012, 21:50  [ТС] #37
Занятно) Ну, можно некоторые моменты переделать. вместо
C++
1
if(thIdx % 2 == 0)
написать
C++
1
if(!(thIdx & 1))
вместо
C++
1
if(in_arr[i] % 2 != 0)
написать
C++
1
if(in_arr[i] & 1)
вместо
C++
1
ulong sq = sqrt(in_arr[i]) + 1;
написать
C++
1
ulong sq = sqrt(in_arr[i]);
но все это мелочи.
может Вам попробовать третий алгоритм так переделать?
0
AEXks
24 / 3 / 1
Регистрация: 28.10.2012
Сообщений: 35
30.10.2012, 21:53 #38
это какой именно? я чет прочитав все что тут было написано так и не понял чем они особо отличаются?
0
Thinker
Эксперт C++
4226 / 2200 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
30.10.2012, 21:56  [ТС] #39
скоростью отличаются. третий алгоритм из поста 1, как минимум, в два раза быстрее чем первый алгоритм. Но это для чисел из диапазона от 2 до 10^8. А при росте чисел прирост скорости будет существенно расти.
0
AEXks
24 / 3 / 1
Регистрация: 28.10.2012
Сообщений: 35
30.10.2012, 22:14 #40
Thinker, а ну да, вы собственно и воспользовались тем, что период последовательности числе будет равен произведению выкинутых. Я написал тестовую прогу для вычисления всего этого и вот что у меня вышло:
число выкинутыхпериод количество оставшихся чисел в периоде процент оставшихся всего
1 1 1 50%
2 8 6 33%
3 8 30 26%
4 48 210 22%
5 480 2310 20%
6 576030.030 19%
7 92.160510.510 18%
8 1.658.8799.699.690 17%
   
Таблица растет очень быстро и не ясно как вводить в начале все эти числа. Поясню: для старта проверки на GPU если мы выкинули например 7 чисел, то нужно их каким то образом сообщить конвееру, чтобы 92160 нитям досталось по числу, и потом мы уже к ним прибавляем так называемый shift, равный периоду (в примере 510 510). собственно инициализировать нужно всего один раз. НО так как число то маленькое для GPU (MAX_ULONG) то я думаю из-за чтений из памяти произойдет даже замедление. Так что надо придумывать для длиной арифметики. А все таки как определить номер старшего бита числа, кроме как
C++
1
2
3
4
5
for( ; dig != 0; )
{
     dig >>= 1;
     ++sum;
}
0
ValeryS
Модератор
6636 / 5043 / 466
Регистрация: 14.02.2011
Сообщений: 16,854
30.10.2012, 23:21 #41
Цитата Сообщение от AEXks Посмотреть сообщение
А все таки как определить номер старшего бита числа, кроме как

C++
1
2
3
4
5
for( ; dig != 0; )
{
 dig >>= 1;
 ++sum;
}
ну можно попробовать так
C++
1
2
3
4
5
6
7
8
9
10
11
for( ; dig != 0; )
{
 dig >>= 8;
 mod= dig&0xFF;
 sum+=8;
}
for( ; mod != 0; )
{
 mod >>= 1;
 ++sum;
}
при числе 0хFFFFFFFFFFFFFFFF
должно получится 16 циклов вместо 64
между ними можно сдвигать еще на 4,2
можно начать сдвигать с 16 с 32

Добавлено через 2 минуты
если первый цикл сделать сдвиг на 32
потом 16,8,4,2,1
то в самом пиковом случае 12 циклов(если я правильно подсчитал)
0
AEXks
24 / 3 / 1
Регистрация: 28.10.2012
Сообщений: 35
31.10.2012, 11:13 #42
ValeryS, попробуем

Добавлено через 21 минуту
ValeryS, что то пример работает не верно. Наверно вы не проверяли результат. В общем вот так надо
C++
1
2
3
4
5
6
7
8
9
10
for( ; dig >= 0xFF; )
{
    dig >>= 8;          
    sum += 8;
}
for( ; dig != 0; )
{
    dig >>= 1;
    ++sum;
}
Для числа, у которого 44 старший бит получаем:
- стандартный алгоритм - 44 битовых операции
- усовершенствованный - 5 + 4 = 9 битовых операций
А для больших чисел наверно можно и увеличить ширину сдвига. Но тогда чем больше ширина сдвига, тем больше нужно сделать сдвигов для маленьких чисел.
Например для самого большого числа в 63 бит:
- при сдвиге в 8 получаем 7 + 7 = 14 БО
- при сдвиге в 16 получаем 3 + 15 = 18 БО
- при сдвиге в 32 получаем 1 + 31 = 32 БО

Думаю 8 это оптимально.
1
Thinker
Эксперт C++
4226 / 2200 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
31.10.2012, 12:03  [ТС] #43
можно использовать двоичный поиск. сложность алгоритма
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// n - количество бит в числе a
int Search(unsigned long long a, int n)
{
   int i = 0;
   while (n)
   {
       n >>= 1;
       if (a >> n)
       {
           i += n;
           a >>= n;
       }
   }
   return i;
}
в среднем будет O(ln n). А сложность алгоритма
C++
1
2
3
4
5
6
7
int Search(unsigned long long a)
{
   int i;
   for(i = -1; a; a >>= 1, i++)
      ;
   return i;
}
в среднем будет O(n). Поэтому первый алгоритм в среднем работает в разы быстрее второго.

Первый алгоритм максимум сделает 6 проверок, второй - 64 проверки. почувствуйте разницу.

Добавлено через 14 минут
Цитата Сообщение от AEXks Посмотреть сообщение
Thinker, а ну да, вы собственно и воспользовались тем, что период последовательности числе будет равен произведению выкинутых.
Я Вам про этот модуль m и писал в предыдущих постах. Увеличивал я именного его. Это и есть период. Странно, а я думал, что Вы понимали меня))
0
Catstail
Модератор
22619 / 10980 / 1779
Регистрация: 12.02.2012
Сообщений: 18,123
31.10.2012, 12:30 #44
Вы будете смеяться... Но самый быстрый алгоритм проверки числа (до 10000) на простоту, на мой взгляд, таков:

Создать упорядоченный массив всех простых чисел от 2 до 9973, а проверяемое число искать двоичным поиском в этом массиве... Проверяться будет "пулей" !
0
Thinker
Эксперт C++
4226 / 2200 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
31.10.2012, 12:35  [ТС] #45
Catstail, смеяться никто не будет. При любом модуле m именно это и происходит при проверке всех простых чисел, меньших числа m (именно двоичный поиск). Это все понятно и просто. самое интересное начинается, когда простые числа в массиве заканчиваются, а проверка на делители продолжается)))
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
31.10.2012, 12:35
Привет! Вот еще темы с ответами:

Проверка числа на простоту - C++
Дано натуральное число N, проверить, простое оно или нет. Увеличить его значение на натуральное число M. Проверить, осталось ли оно ...

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

Проверка числа на простоту (нужны комментарии) - C++
объясните пожалуйста, как в данной функции выполняется проверка числа на простоту. как можно поподробнее bool Prime(int const num)//...

Робота с динамической памятью, проверка числа на простоту - C++
В динамическую память последовательно занести введенные с клавиатуры целые числа (признак завершения ввода - число ноль). Проверить все...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
31.10.2012, 12:35
Ответ Создать тему
Опции темы

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