Какой самый быстрый алгоритм поиска простых чисел?

184

Какой самый быстрый алгоритм для определения простых чисел с помощью C ++? Я использовал алгоритм сита, но все еще хочу, чтобы он был быстрее!

kasperasky
источник
Старая статья, которую я нашел, но выглядит интересной: Fun with Prime Numbers
Mvcoile
29
@ Jaider это терпит неудачу для чисел всего 7 (111). Это также терпит неудачу для 1001 = 9. И очевидно, что это не работает почти для всех простых чисел в целом (не распространяется на случай 2 ^ p - 1, которые являются простыми числами Мерсенна - классически сгенерированные примеры - которые всегда будут иметь вид 111 ... 1)
Даниэль Кац
1
@Kasperasky - Вы не упомянули, какое сито? Вы, вероятно, имеете в виду сито из эрантозов!
user2618142
Алгоритм
сита

Ответы:

79

Очень быстрое внедрение « Сита Аткина» - праймэн Дана Бернштейна . Это сито более эффективно, чем сито Эратосфена . Его страница содержит некоторую информацию о тестах.

Грег Хьюгилл
источник
10
На самом деле я не думаю, что Primegen самый быстрый или даже второй самый быстрый; Я думаю, что yafu и primesieve быстрее в общем и, конечно, больше 2 ^ 32. Оба представляют собой (модифицированные) сита Эратосфена, а не сита Аткина-Бернштейна.
Чарльз
6
Первичное сито с эратосфенами (SoE) является самым быстрым из возможных алгоритмов и всегда будет быстрее, чем любая реализация Sieve of Atkin SoA, включая Bernstein, как указано в этом ответе, поскольку простое сито уменьшает количество операций по сравнению с SoA: для 32- в диапазоне битовых чисел (2 ^ 32 - 1), primesieve выполняет около 1,2 миллиарда вызовов, в то время как SoA выполняет в общей сложности около 1,4 миллиарда комбинированных операций без тумблеров и квадратов, причем обе операции имеют примерно одинаковую сложность и могут быть оптимизированы примерно одинаково путь.
GordonBGood
7
Продолжение: Бернштейн сравнил только SoE, используя ту же эффективную факторизацию колеса, что и для SoA, которое представляет собой колесо 2; 3; 5, использование которого приводит к получению около 1,83 млрд. Бросков в диапазоне 32-битных чисел; это делает SoA примерно на 30% быстрее при сравнении этой ограниченной версии SoE для эквивалентных других оптимизаций. Тем не менее, алгоритм простых чисел использует колесо 2; 3; 5; 7 в сочетании с предварительным отбрасыванием сегмента колеса 2; 3; 5; 7; 11; 13; 17, чтобы сократить количество операций примерно до 1,2 млрд. 16,7% быстрее, чем SoA с эквивалентными оптимизациями цикла работы.
GordonBGood
6
Продолжение2: у SoA con нет факторизации колеса с более высоким коэффициентом, используемой для значительной разницы, поскольку колесо факторизации 2; 3; 5 является «запеченной» частью алгоритма.
GordonBGood
4
@ Eamon Nerbonne, WP правильно; однако, просто немного лучшая вычислительная сложность не делает быстрые алгоритмы для общего использования. В этих комментариях я имею в виду, что максимальная факторизация колеса сита эратосфена (SoE) (что невозможно для сита Atkin-SoA) приводит к несколько меньшим операциям для SoE до диапазона около миллиарда. Гораздо выше этого уровня обычно нужно использовать сегментацию страниц, чтобы преодолеть ограничения памяти, и именно здесь происходит сбой SoA, что приводит к быстрому увеличению количества постоянных издержек с увеличением диапазона.
GordonBGood
29

Если это должно быть очень быстро, вы можете включить список простых чисел:
http://www.bigprimes.net/archive/prime/

Если вам просто нужно знать, является ли определенное число простым числом, в википедии перечислены различные простые тесты . Они, вероятно , самый быстрый способ , чтобы определить , если большие числа простых чисел, особенно потому , что они могут сказать вам , если число не простое.

Георг Шолли
источник
2
Список всех простых чисел? Я думаю, что вы имеете в виду список первых нескольких простых чисел ... :)
j_random_hacker
9
Если вы звоните 100000000 несколько, то да. :)
Георг Шолли
58
наверняка 100000000 - это «несколько» по сравнению с бесконечностью;)
Тимофей
9
Почему вы думаете, что Сито Аткина (SoA) быстрее, чем Сито Эратосфена (SoE)? Конечно, это не так, когда кто-то просто реализует программу с использованием псевдокода, как в статье Википедии, которую вы связали. Если SoE реализован с таким же уровнем возможных оптимизаций, который используется с SoA, то для очень больших диапазонов просеивания для SoA немного меньше операций, чем для SoE, но этот выигрыш обычно более чем компенсируется повышенной сложностью и дополнительные издержки постоянного коэффициента этой вычислительной сложности, так что для практических приложений SoE лучше.
GordonBGood
26

Он, он, я знаю, что я некромант, отвечающий на старые вопросы, но я только что нашел этот вопрос, ища в сети способы реализации эффективных тестов простых чисел.

До сих пор я считаю, что самый быстрый алгоритм тестирования простых чисел - это Strong Probable Prime (SPRP). Я цитирую форумы Nvidia CUDA:

Одна из наиболее практичных проблем ниши в теории чисел связана с идентификацией простых чисел. Учитывая N, как вы можете эффективно определить, является ли оно простым или нет? Это не просто теоретическая проблема, это может быть реальная проблема, необходимая в коде, возможно, когда вам нужно динамически найти размер основной хеш-таблицы в определенных диапазонах. Если N что-то порядка 2 ^ 30, вы действительно хотите провести 30000 тестов с делением, чтобы найти какие-либо факторы? Очевидно нет.

Общепринятое практическое решение этой проблемы - это простой тест, называемый тестом вероятного простого числа Эйлера, и более мощное обобщение, называемое сильным вероятным простым числом (SPRP). Это тест, который для целого числа N может вероятностно классифицировать его как простое или нет, а повторные тесты могут увеличить вероятность правильности. Медленная часть самого теста в основном включает вычисление значения, аналогичного A ^ (N-1) по модулю N. Любой, кто реализует варианты шифрования с открытым ключом RSA, использовал этот алгоритм. Это полезно как для больших целых чисел (например, 512 бит), так и для обычных 32 или 64 битных целых.

Тест может быть изменен с вероятностного отклонения на окончательное доказательство первичности путем предварительного вычисления определенных входных параметров теста, которые, как известно, всегда успешны для диапазонов N. К сожалению, обнаружение этих «самых известных тестов» фактически является поиском огромного ( фактически бесконечный) домен. В 1980 году Карл Померанс (Carl Pomerance) создал первый список полезных тестов (известный тем, что он вычисляет RSA-129 с помощью алгоритма Quadratic Seive). Позднее Йешке значительно улучшил результаты в 1993 году. В 2004 году Чжан и Тан улучшили теорию и пределы поискового домена. Greathouse и Livingstone опубликовали самые современные результаты до сих пор в Интернете, по адресу http://math.crg4.com/primes.html , лучшие результаты огромного поискового домена.

Смотрите здесь для получения дополнительной информации: http://primes.utm.edu/prove/prove2_3.html и http://forums.nvidia.com/index.php?showtopic=70483

Если вам просто нужен способ генерирования очень больших простых чисел и вы не хотите генерировать все простые числа <целое число n, вы можете использовать тест Лукаса-Лемера для проверки простых чисел Мерсенна. Простое число Мерсенна имеет вид 2 ^ p -1. Я думаю, что тест Лукаса-Лемера - самый быстрый алгоритм, открытый для простых чисел Мерсенна.

И если вы хотите использовать не только самый быстрый алгоритм, но и самое быстрое оборудование, попробуйте реализовать его с помощью Nvidia CUDA, написать ядро ​​для CUDA и запустить его на GPU.

Вы даже можете заработать немного денег, если обнаружите достаточно большие простые числа, EFF раздает призы от $ 50K до $ 250K: https://www.eff.org/awards/coop

Mack
источник
17

Существует 100% математический тест, который проверяет, является ли число Pпростым или составным, называется AKS Primality Test .

Концепция проста: при заданном числе P, если все коэффициенты (x-1)^P - (x^P-1)делятся на P, то Pэто простое число, в противном случае это составное число.

Например, учитывая, дал P = 3бы полином:

   (x-1)^3 - (x^3 - 1)
 = x^3 + 3x^2 - 3x - 1 - (x^3 - 1)
 = 3x^2 - 3x

И коэффициенты делятся на 3, поэтому число является простым.

И пример, где P = 4, который НЕ простое число приведет к:

   (x-1)^4 - (x^4-1)
 = x^4 - 4x^3 + 6x^2 - 4x + 1 - (x^4 - 1)
 = -4x^3 + 6x^2 - 4x

И здесь мы можем видеть, что коэффициенты 6не делятся на 4, следовательно, это НЕ простое число.

Полином (x-1)^PбудетP+1 термины и может быть найден с использованием комбинации. Итак, этот тест будет выполняться во O(n)время выполнения, поэтому я не знаю, насколько это было бы полезно, так как вы можете просто выполнить итерацию iот 0 до pи проверить оставшуюся часть.

Kousha
источник
5
AKS - очень медленный метод на практике, не конкурирующий с другими известными методами. Метод, который вы описываете, не AKS, а вводная лемма, которая медленнее, чем неоптимизированное пробное деление (как вы указали).
DanaJ
привет @ Kousha, что xобозначает стенды? в (x-1)^P - (x^P-1). у вас есть пример кода для этого? в C ++ для определения, является ли целое число простым или нет?
kiLLua
@kiLLua X это просто переменная. Это коэффициент X, который определяет, является ли число простым или нет. И нет, у меня нет кода. Я не рекомендую использовать этот метод для определения, является ли число простым или нет. Это просто очень крутое математическое поведение простых чисел, но в остальном это невероятно неэффективно.
Куша
5

Ваша задача решить, является ли конкретное число простым? Тогда вам нужен тест на простоту (легкий). Или вам нужно все простые числа до заданного числа? В этом случае простые сита хороши (легко, но требуют памяти). Или вам нужны главные факторы числа? Это потребует факторизации (сложно для больших чисел, если вы действительно хотите наиболее эффективные методы). Насколько большие цифры вы смотрите? 16 бит? 32 бита? больше?

Один умный и эффективный способ - это предварительно вычислить таблицы простых чисел и сохранить их в файле с использованием кодирования на битовом уровне. Файл считается одним длинным битовым вектором, тогда как бит n представляет целое число n. Если n простое, его бит устанавливается в единицу и в противном случае равен нулю. Поиск очень быстрый (вы вычисляете смещение байта и битовую маску) и не требует загрузки файла в память.

Кристиан Линдиг
источник
Хороший тест на простоту конкурирует с задержкой основной памяти для простых таблиц, которые могут разумно соответствовать, поэтому я бы не стал использовать это, если бы он не подходил для L2.
Чарльз
3

Рабин-Миллер является стандартным вероятностным тестом простоты. (вы запускаете его K раз, и входное число либо однозначно составное, либо, вероятно, оно простое с вероятностью ошибки 4 -K . (несколько сотен итераций, и почти наверняка это говорит вам правду)

Существует не вероятностный (детерминистский) вариант Рабина Миллера .

Great Internet Mersenne Prime Search (GIMPS) , который нашел мировой рекорд по величине доказанным штрихом (2 74,207,281 - 1 по состоянию на июнь 2017 года), использует несколько алгоритмов , но это простые числа в специальных формах. Однако приведенная выше страница GIMPS включает в себя некоторые общие детерминированные тесты первичности. Похоже, они указывают на то, что алгоритм является «самым быстрым», зависит от размера проверяемого числа. Если ваше число соответствует 64 битам, то вам, вероятно, не следует использовать метод, предназначенный для работы с простыми числами из нескольких миллионов цифр.

Джейсон С
источник
2

Это зависит от вашего приложения. Есть несколько соображений:

  • Вам нужна только информация о том, являются ли несколько чисел простыми, нужны ли все простые числа до определенного предела или вам (потенциально) нужны все простые числа?
  • Насколько велики числа, с которыми вам приходится иметь дело?

Тесты Миллера-Рабина и аналоговые тесты выполняются только быстрее, чем сито для чисел более определенного размера (я полагаю, где-то около нескольких миллионов). Ниже, используя пробное деление (если у вас есть только несколько чисел) или сито быстрее.

Сванте
источник
0

Я дам вам решить, будет ли это быстрее или нет.

using System;
namespace PrimeNumbers
{

public static class Program
{
    static int primesCount = 0;


    public static void Main()
    {
        DateTime startingTime = DateTime.Now;

        RangePrime(1,1000000);   

        DateTime endingTime = DateTime.Now;

        TimeSpan span = endingTime - startingTime;

        Console.WriteLine("span = {0}", span.TotalSeconds);

    }


    public static void RangePrime(int start, int end)
    {
        for (int i = start; i != end+1; i++)
        {
            bool isPrime = IsPrime(i);
            if(isPrime)
            {
                primesCount++;
                Console.WriteLine("number = {0}", i);
            }
        }
        Console.WriteLine("primes count = {0}",primesCount);
    }



    public static bool IsPrime(int ToCheck)
    {

        if (ToCheck == 2) return true;
        if (ToCheck < 2) return false;


        if (IsOdd(ToCheck))
        {
            for (int i = 3; i <= (ToCheck / 3); i += 2)
            {
                if (ToCheck % i == 0) return false;
            }
            return true;
        }
        else return false; // even numbers(excluding 2) are composite
    }

    public static bool IsOdd(int ToCheck)
    {
        return ((ToCheck % 2 != 0) ? true : false);
    }
}
}

На моем ноутбуке Core 2 Duo с процессором 2,40 ГГц процесс поиска и печати простых чисел в диапазоне от 1 до 1 000 000 занимает около 82 секунд . И найдено 78 498 простых чисел.

Тайяб Мажар
источник
3
это слишком медленно. проблема в том i <= (ToCheck / 3). так и должно быть i <= (ToCheck / i). с этим, это могло бы бежать через 0,1 секунды вместо этого.
Уилл Несс
-1

Я всегда использую этот метод для вычисления чисел простых чисел, следующих за алгоритмом сита.

void primelist()
 {
   for(int i = 4; i < pr; i += 2) mark[ i ] = false;
   for(int i = 3; i < pr; i += 2) mark[ i ] = true; mark[ 2 ] = true;
   for(int i = 3, sq = sqrt( pr ); i < sq; i += 2)
       if(mark[ i ])
          for(int j = i << 1; j < pr; j += i) mark[ j ] = false;
  prime[ 0 ] = 2; ind = 1;
  for(int i = 3; i < pr; i += 2)
    if(mark[ i ]) ind++; printf("%d\n", ind);
 }
Осман Гони Нахид
источник
-3
#include<stdio.h>
main()
{
    long long unsigned x,y,b,z,e,r,c;
    scanf("%llu",&x);
    if(x<2)return 0;
    scanf("%llu",&y);
    if(y<x)return 0;
    if(x==2)printf("|2");
    if(x%2==0)x+=1;
    if(y%2==0)y-=1;
    for(b=x;b<=y;b+=2)
    {
        z=b;e=0;
        for(c=2;c*c<=z;c++)
        {
            if(z%c==0)e++;
            if(e>0)z=3;
        }
        if(e==0)
        {
            printf("|%llu",z);
            r+=1;
        }
    }
    printf("|\n%llu outputs...\n",r);
    scanf("%llu",&r);
}    
Tjandra
источник
r используется до инициализации
zumalifeguard
-3

Я не знаю ни одного предопределенного алгоритма, но я создал свой собственный, который очень быстрый. Он может обрабатывать 20 цифр менее чем за 1 секунду. Максимальная возможность этой программы составляет 18446744073709551615. Программа:

#include <iostream>
#include <cmath>
#include <stdlib.h>

using namespace std;

unsigned long long int num = 0;

bool prime() {
    if (num % 2 == 0 || num == 1) {
        return false;
    }

    unsigned long int square_root = sqrt(num);
    for (unsigned long int i = 3; i <= square_root; i += 2) {
        if (num % i == 0) {
            return false;
        }
    }

    return true;
}

int main() {
    do {
        system("cls");
        cout << "Enter number : ";
        cin >> num;

        if (prime()) {
            cout << "The number is a prime number" << endl << endl << endl << endl;
        } else {
            cout << "The number is not a prime number" << endl << endl << endl << endl;
        }
        system("pause");
    } while (1);

    return 0;
}
Sushant
источник
-4
#include <iostream>

using namespace std;

int set [1000000];

int main (){

    for (int i=0; i<1000000; i++){
        set [i] = 0;
    }
    int set_size= 1000;
    set [set_size];
    set [0] = 2;
    set [1] = 3;
    int Ps = 0;
    int last = 2;

    cout << 2 << " " << 3 << " ";

    for (int n=1; n<10000; n++){
        int t = 0;
        Ps = (n%2)+1+(3*n);
        for (int i=0; i==i; i++){
            if (set [i] == 0) break;
            if (Ps%set[i]==0){
                t=1;
                break;
            }
        }
        if (t==0){
            cout << Ps << " ";
            set [last] = Ps;
            last++;
        }
    }
    //cout << last << endl;


    cout << endl;

    system ("pause");
    return 0;
}
Видура
источник
12
это должен быть ответ на вопрос «Как писать неструктурированный код без фактического использования GOTO». Все это путаница просто для кодирования простого пробного деления! (n%2)+1+(3*n)вроде мило, хотя. :)
Уилл Несс
1
@ Уилл Несс, я бы проголосовал за это как за ответ на этот вопрос; зачем использовать цикл for, когда макрос будет делать? :)
Роб Грант
-4

Я знаю, что это немного позже, но это может быть полезно для людей, прибывающих сюда из поисков. В любом случае, вот некоторый JavaScript, который основывается на том факте, что нужно проверять только простые факторы, поэтому более ранние простые числа, сгенерированные кодом, повторно используются в качестве тестовых факторов для более поздних. Конечно, все четные значения и значения mod 5 отфильтровываются первыми. Результат будет в массиве P, и этот код может обработать 10 миллионов простых чисел менее чем за 1,5 секунды на ПК i7 (или 100 миллионов примерно за 20). Переписано на С это должно быть очень быстро.

var P = [1, 2], j, k, l = 3

for (k = 3 ; k < 10000000 ; k += 2)
{
  loop: if (++l < 5)
  {
    for (j = 2 ; P[j] <= Math.sqrt(k) ; ++j)
      if (k % P[j] == 0) break loop

    P[P.length] = k
  }
  else l = 0
}
Робин Никсон
источник
2
Это доставит вам много хлопот, если вы генерируете большое количество простых чисел, и для сравнений лучше использовать P [j] * P [j] <= k, потому что sqrt довольно медленный
Simon
-11
#include<iostream>
using namespace std;

void main()
{
    int num,i,j,prime;
    cout<<"Enter the upper limit :";
    cin>>num;

    cout<<"Prime numbers till "<<num<<" are :2, ";

    for(i=3;i<=num;i++)
    {
        prime=1;
        for(j=2;j<i;j++)
        {
            if(i%j==0)
            {
                prime=0;
                break;
            }
        }

        if(prime==1)
            cout<<i<<", ";

    }
}
Gaurav
источник
60
это самое медленное, что вы можете сделать.
Уилл Несс
1
Это очень медленно, если верхний предел, скажем, 10000000, то этот код будет занимать много времени!
Диксит Сингла
этот код O (N ^ 2 / log N). без break;этого было бы еще медленнее, O (N ^ 2), но это уже можно рассматривать как ошибку кодирования. сохранение и тестирование по простым числам - O (N ^ 2 / (log N) ^ 2), а тестирование по простым числам ниже квадратного корня числа - O (N ^ 1.5 / (log N) ^ 2).
Уилл Несс
@WillNess Возможно, немного гиперболический. Он мог бы легко запустить цикл for с 1 вместо 2 и добавить j <= i вместо j <i. :)
Кенни Кейсон
3
Я не думаю, что этот пост должен быть удален, он служит ценным контрпримером.
Уилл Несс