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

Очень быстрая реализация Сито Аткина - это Primegen Дэна Бернштейна. Это сито более эффективно, чем Сито Эратосфена. На его странице есть контрольная информация.

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

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

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

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

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

Есть маловероятный (детерминированный) вариант Рабина Миллера.

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

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

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

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

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

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

One of the more practical niche problems in number theory has to do with identification of prime numbers. Given N, how can you efficiently determine if it is prime or not? This is not just a thoeretical problem, it may be a real one needed in code, perhaps when you need to dynamically find a prime hash table size within certain ranges. If N is something on the order of 2^30, do you really want to do 30000 division tests to search for any factors? Obviously not.

The common practical solution to this problem is a simple test called an Euler probable prime test, and a more powerful generalization called a Strong Probable Prime (SPRP). This is a test that for an integer N can probabilistically classify it as prime or not, and repeated tests can increase the correctness probability. The slow part of the test itself mostly involves computing a value similar to A^(N-1) modulo N. Anyone implementing RSA public-key encryption variants has used this algorithm. It's useful both for huge integers (like 512 bits) as well as normal 32 or 64 bit ints.

The test can be changed from a probabilistic rejection into a definitive proof of primality by precomputing certain test input parameters which are known to always succeed for ranges of N. Unfortunately the discovery of these "best known tests" is effectively a search of a huge (in fact infinite) domain. In 1980, a first list of useful tests was created by Carl Pomerance (famous for being the one to factor RSA-129 with his Quadratic Seive algorithm.) Later Jaeschke improved the results significantly in 1993. In 2004, Zhang and Tang improved the theory and limits of the search domain. Greathouse and Livingstone have released the most modern results until now on the web, at http://math.crg4.com/primes.html, the best results of a huge search domain.

См. Здесь для получения дополнительной информации: 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 разыгрывает призы от 50 до 250 тысяч долларов: https://www.eff.org/awards/coop

#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);
}    

#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;
}

#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<<", ";

    }
}

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

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
}

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

Идея проста: для числа 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 и проверять оставшееся.

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

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);
 }

Я позволю вам решить, самый быстрый он или нет.

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);
    }
}
}

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

Я написал его сегодня на C, скомпилировал с помощью tcc, разобрался во время подготовки к экзаменам несколько лет назад. не знаю, написал ли кто это уже сейчас. это действительно быстро (но вы должны решить, быстро это или нет). потребовалась одна или две минуты, чтобы найти около 100 004 простых числа от 10 до 1000000 на процессоре i7 при средней загрузке процессора 32%. как вы знаете, простыми могут быть только те, у которых последняя цифра либо 1,3,7, либо 9 и чтобы проверить, является ли это число простым или нет, вы должны разделить это число только на ранее найденные простые числа. поэтому сначала возьмите группу из четырех чисел = {1,3,7,9}, проверить это делением на известные простые числа, если напоминание не равно нулю, то число простое, добавьте его в массив простых чисел. затем добавьте 10 в группу, чтобы она стала {11,13,17,19}, и повторите процесс.

#include <stdio.h>
int main() {    
    int nums[4] = {1,3,7,9};
    int primes[100000];
    primes[0]=2;
    primes[1]=3;
    primes[2]=5;
    primes[3]=7;
    int found = 4;
    int got = 1;
    int m=0;
    int upto = 1000000;
    for(int i=0;i<upto;i++){
        //printf("iteration number: %d\n",i);
        for(int j=0;j<4;j++){
            m = nums[j]+10;
            //printf("m = %d\n",m);
            nums[j] = m;
            got = 1;
            for(int k=0;k<found;k++){
                //printf("testing with %d\n",primes[k]);
                if (m%primes[k]==0){
                    got = 0;
                    //printf("%d failed for %d\n",m,primes[k]);
                    break;
                }
            }
            if (got==1){
                //printf("got new prime: %d\n",m);
                primes[found]= m;
                found++;
            }
        }
    }
    printf("found total %d prime numbers between 1 and %d",found,upto*10);
    return 0;
}

#include <stdio.h>

int main() //works for first 10000 primes.
{
#define LEAST_PRIME 2

int remainder, number_to_be_checked = LEAST_PRIME, divisor = 2, remainder_dump, 
upper_limit; //upper limit to be specified by user.
int i = 1;
printf("            SPECIFY UPPER LIMIT:   ");
scanf("%d", &upper_limit);
printf("1. 2,\n", number_to_be_checked); //PRINTS 2.
do
{
    remainder_dump = 1;
    divisor = 2;

    do
    {
        remainder = number_to_be_checked % divisor;
        if (remainder == 0)
        {
            remainder_dump = remainder_dump * remainder; // dumping 0 for rejection.
        }
        ++divisor;

    } while (divisor <= number_to_be_checked/divisor); // upto here we know number is prime or 
not.
    if (remainder_dump != 0)
    {
        ++i;
        printf("%d.) %d.\t", i, number_to_be_checked); //print if prime.
    };
    number_to_be_checked = number_to_be_checked + 1;
} while (number_to_be_checked <= upper_limit);
printf("\nNUMBER OF PRIMES:           \t%d", i);

return 0;
}

Это может бесконечно перечислять простые числа. Извините за объем, я написал эту программу, когда я был всего 3 дня в программировании, поэтому она использует очень простые функции. После редактирования, предложенного в разделе комментариев, он печатает простое до 1000000 за 13 секунд.

Вы можете попробовать этот код, самый быстрый способ получить простое число с меньшим количеством циклов, такое число, как 1000, получит менее 15 циклов

def divisors(integer):
    result = []
    i = 2
    j = integer/2
    while(i <= j):
        if integer % i == 0:
            result.append(i)
            if i != integer//i:
                result.append(integer//i)
        i += 1
        j = integer//i
    if len(result) > 0:
        return sorted(result)
    else:
        return f"{integer} is prime"


print(divisors(1827))
print(divisors(1025))
print(divisors(27))

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

// built on core-i2 e8400
// Benchmark from PowerShell
// Measure-Command { ExeName.exe }
// Days              : 0
// Hours             : 0
// Minutes           : 0
// Seconds           : 23
// Milliseconds      : 516
// Ticks             : 235162598
// TotalDays         : 0.00027217893287037
// TotalHours        : 0.00653229438888889
// TotalMinutes      : 0.391937663333333
// TotalSeconds      : 23.5162598
// TotalMilliseconds : 23516.2598
// built with latest MSVC
// cl /EHsc /std:c++latest main.cpp /O2 /fp:fast /Qpar

#include <cmath>
#include <iostream>
#include <vector>

inline auto prime = [](std::uint64_t I, std::vector<std::uint64_t> &cache) -> std::uint64_t {
    std::uint64_t root{static_cast<std::uint64_t>(std::sqrtl(I))};
    for (std::size_t i{}; cache[i] <= root; ++i)
        if (I % cache[i] == 0)
            return 0;

    cache.push_back(I);
    return I;
};

inline auto prime_sum = [](std::uint64_t S) -> std::uint64_t {
    std::uint64_t R{5};
    std::vector<std::uint64_t> cache;
    cache.reserve(S / 16);
    cache.push_back(3);

    for (std::uint64_t I{5}; I <= S; I += 8)
    {
        std::uint64_t U{I % 3};
        if (U != 0)
            R += prime(I, cache);
        if (U != 1)
            R += prime(I + 2, cache);
        if (U != 2)
            R += prime(I + 4, cache);
        R += prime(I + 6, cache);
    }
    return R;
};

int main()
{
    std::cout << prime_sum(63210123);
}