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

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

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

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

29.09.2012, 21:35. Просмотров 46284. Ответов 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++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
AEXks
24 / 3 / 1
Регистрация: 28.10.2012
Сообщений: 35
01.11.2012, 19:26     Быстрая проверка натурального числа на простоту #61
ValeryS, да, я там потом решил этот вопрос, все дело было в этом операторе:
C++
1
ulong d = 1 << 35;
а надо было
C++
1
ulong d = (ulong)1 << 35;
Добавлено через 9 часов 24 минуты
Thinker, в общем написал алгоритм, может его стоит оптимизировать, потому что по скорости он проигрывает в 8 раз! и уже для 128 битных чисел нужно много времени. Даже для числа 265 252 859 812 191 058 636 308 479 999 999 (11*3 = 33 знака) нужно проверить 1,6 * 1016 делителей. И если скорость 2 * 109 / сек, то получаем 1,6 * 1016 / (2 * 109) = 8 * 106 сек или 92 дня.

Вот собственно функции:
mask[i] хранит заранее записанную маску, у которой все единицы начиная от самого левого бита и до i, или по простому - выделяем i бит слева.
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
inline __device__ void Search(ulong a,int n, int &ret)
{
    while (n)
    {
        n >>= 1;
        if (a >> n)
        {
            ret += n;
            a >>= n;
        }
    }
}
 
__device__ void LongMod(ulong *digit, ulong count, ulong modl, int bit, ulong &ret)
{
    int how_bit = BIT;
 
    ulong digit_del = digit[0];
    ulong part = digit[1];
    ulong mod = 0;
 
    mod = digit_del % modl;
    for( ;how_bit > 0; )
    {       
        int bitLeft = 0;
        Search(mod,bit,bitLeft);
        bitLeft = BIT - bitLeft - 1;
        if(how_bit >= bitLeft)
        {
            digit_del = mod << bitLeft;
            digit_del |= (part & mask[bitLeft]) >> (BIT - bitLeft);
            part <<= bitLeft;
            how_bit -= bitLeft;
        }
        else if(how_bit > 0)
        {
            digit_del = mod << how_bit;
            digit_del |= (part & mask[how_bit]) >> (BIT - how_bit);
            how_bit = 0;
        }
        mod = digit_del % modl;
    }
    ret = mod;
}
Thinker
Эксперт C++
4225 / 2199 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
01.11.2012, 19:39  [ТС]     Быстрая проверка натурального числа на простоту #62
AEXks, ну, ваше стремление похвально, но а на что вы расчитывали, используя длинную арифметику и алгоритм проверки на простоту экспоненциальной сложности относительно количества цифр. Так и должно быть, поэтому я побаловался этим и забросил))
Вы поймите, алгоритм должен зависеть не от аппаратуры (CPU, GPU и т.д.), а от теоретической сложности, а иначе смысла не было бы во многих криптоалгоритмах
AEXks
24 / 3 / 1
Регистрация: 28.10.2012
Сообщений: 35
01.11.2012, 19:43     Быстрая проверка натурального числа на простоту #63
так алгоритм АКС быстрее это делает?
Thinker
Эксперт C++
4225 / 2199 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
01.11.2012, 19:45  [ТС]     Быстрая проверка натурального числа на простоту #64
если честно, то не знаю, времени не было его проверить. но у него заявленная сложность полиномиальная относительно количества цифр, то есть обещает быть быстрым. но оять же, не настолько быстрым, чтобы какие-то криптоалгоритмы упали бы.
AEXks
24 / 3 / 1
Регистрация: 28.10.2012
Сообщений: 35
01.11.2012, 20:22     Быстрая проверка натурального числа на простоту #65
Thinker, может попробуете тогда для CPU реализовать хотя бы?
Thinker
Эксперт C++
4225 / 2199 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
01.11.2012, 21:03  [ТС]     Быстрая проверка натурального числа на простоту #66
надо будет теоремы почитать с доказательствами, а иначе нет смысла алгоритм составлять. будет время, посмотрю. с другой стороны, почему его так и не реализовали, по крайней мере, не видел реализацию. это, наверное, потому что есть гипотеза (недоказанная), которая значительно ускоряет алгоритм AKS
AEXks
24 / 3 / 1
Регистрация: 28.10.2012
Сообщений: 35
01.11.2012, 21:34     Быстрая проверка натурального числа на простоту #67
Thinker, на паскале вроде говорят есть реализация
Thinker
Эксперт C++
4225 / 2199 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
01.11.2012, 21:38  [ТС]     Быстрая проверка натурального числа на простоту #68
AEXks, как же вас зацепила эта задача) может вам имеет смысл в сторону вероятностных алгоритмов посмотреть
AEXks
24 / 3 / 1
Регистрация: 28.10.2012
Сообщений: 35
01.11.2012, 21:47     Быстрая проверка натурального числа на простоту #69
Thinker, они же не дают точный результат
Thinker
Эксперт C++
4225 / 2199 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
01.11.2012, 21:49  [ТС]     Быстрая проверка натурального числа на простоту #70
ну, да, а другие алгоритмы (детерминированные) не отличаются скоростью. нужен компромисс)
AEXks
24 / 3 / 1
Регистрация: 28.10.2012
Сообщений: 35
01.11.2012, 21:50     Быстрая проверка натурального числа на простоту #71
Thinker, а вероятностные на много быстрее?
Thinker
Эксперт C++
4225 / 2199 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
01.11.2012, 21:51  [ТС]     Быстрая проверка натурального числа на простоту #72
конечно, а иначе не было бы смысла в их использовании.
Тамика
Котовчанин
870 / 450 / 143
Регистрация: 16.02.2010
Сообщений: 2,954
Записей в блоге: 27
22.01.2014, 18:38     Быстрая проверка натурального числа на простоту #73
Написала когда-то программку, которая, с использованием решета Эратосфена, находит все простые и возвращает самый большой простой делитель числа. Код не идеален, потому как новичок ещё я, но работает быстро.
Буду рада советам!

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
65
66
67
68
69
#include <iostream>
#include <cassert>
#include <math.h>
#include <sstream>
#include <string>
#include <vector>
 
 
std::vector<int> sieve(int num)
{
    int p = 2;
    std::vector <int> s;
    for (int i = 0; i < num; i++)
    {
        s.push_back(i);
    }
    s.at(1) = 1;
 
    while (p < num)
    {
        if (s.at(p)!=0)
        {
        for (int i = p*2; i < num; i += p)
            {
                 s.at(i) = 0;
            }
        }
        p++;
    }
    return s;
}
 
int prime_factor(std::vector<int> vec, unsigned long long div)
{
    int prime = 0;
    for (int i = 0; i < std::sqrtl(div) - 1; i++)
    {
        if (vec.at(i) == 0) {continue;}
        if (div % vec.at(i) == 0)
        {
            prime = vec.at(i);
        }
        i++;
    }
    return prime;
}
 
int solve(unsigned long long num)
{
    std::vector<int> array; 
    int prime;
    int count = std::sqrtl(num);
    array = sieve(count);
    prime = prime_factor(array, num);
    return prime;
}
 
void main(int argc, char *argv[])
{
    unsigned long long arg = 1;
    if (argc >= 1)
    {
        std::stringstream ss;
        ss << argv[1];
        ss >> arg;
    }
    std::cout << solve(arg) << std::endl;
 
}
murderer
3197 / 1420 / 72
Регистрация: 06.10.2010
Сообщений: 3,073
18.07.2014, 12:07     Быстрая проверка натурального числа на простоту #74
А все таки как определить номер старшего бита числа
C
1
2
3
4
5
6
7
8
int __declspec(naked) _cdecl bsr(int x)
{
    _asm
    {
        bsr eax,[esp+4]
        ret
    }
}
Добавлено через 9 минут
А ещё на AMD есть какой-то сумасшедший набор инструкций - TBM, возможно его удастся применить к этой задаче.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.07.2014, 12:34     Быстрая проверка натурального числа на простоту
Еще ссылки по теме:
Проверка на простоту числа C++
Проверка числа на простоту (нужны комментарии) C++
C++ Проверка на простоту числа - исправить ошибки в коде
C++ Робота с динамической памятью, проверка числа на простоту
Проверка цифр натурального числа C++

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

Или воспользуйтесь поиском по форуму:
Psilon
Master of Orion
Эксперт .NET
5882 / 4779 / 633
Регистрация: 10.07.2011
Сообщений: 14,399
Записей в блоге: 5
Завершенные тесты: 4
18.07.2014, 12:34     Быстрая проверка натурального числа на простоту #75
Мне кажется, простейший способ - написать прогармму с кодогенерацией, которая сгенерирует метод, который будет проверять все числа Например взять первые 100 простых чисел, и сгенерировать файлик, где
C++
1
2
3
4
5
6
7
8
if (x == a1 || x == a2 || ...)
   return false;
int sqrt = sqrt_int(x);
int step = std::accumulate(...) //тут получаем произведение всех этих простых чисел. Хотя тут уже double наверное нужно юзать, в int вряд ли влезет
for(int i = 0; i < sqrt; i+=)
   if (x%i == 0)
      return false;
return true;
достаточно заранее найти 100 первых простых чисел (тем же эратосфеном).
Yandex
Объявления
18.07.2014, 12:34     Быстрая проверка натурального числа на простоту
Ответ Создать тему
Опции темы

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