Qual é o algoritmo mais rápido para encontrar números primos?

Qual é o algoritmo mais rápido para descobrir números primos usando C ++? Eu usei o algoritmo de peneira, mas ainda quero que seja mais rápido!

Uma implementação muito rápida da Peneira de Atkin é o primegen de Dan Bernstein . Essa peneira é mais eficiente que a peneira de Eratóstenes . Sua página tem algumas informações de referência.

Se for realmente rápido, você pode incluir uma lista de números primos:
http://www.bigprimes.net/archive/prime/

Se você apenas precisa saber se um determinado número é um número primo, existem vários testes primos listados na wikipedia . Eles provavelmente são o método mais rápido para determinar se números grandes são primos, especialmente porque eles podem dizer se um número não é primo.

Ele, ele, eu sei que sou um necromante de perguntas respondendo a perguntas antigas, mas acabei de encontrar essa pergunta pesquisando na rede maneiras de implementar testes eficientes de números primos.

Até agora, acredito que o algoritmo de teste de número primo mais rápido é o Strong Probable Prime (SPRP). Estou citando nos fóruns da Nvidia CUDA:

Um dos problemas de nicho mais práticos da teoria dos números tem a ver com a identificação de números primos. Dado N, como você pode determinar com eficiência se é primo ou não? Este não é apenas um problema teórico, pode ser um problema real necessário no código, talvez quando você precise encontrar dinamicamente um tamanho de tabela de hash principal dentro de determinados intervalos. Se N é algo da ordem de 2 ^ 30, você realmente deseja fazer 30000 testes de divisão para procurar algum fator? Obviamente não.

A solução prática comum para esse problema é um teste simples chamado teste provável de Euler, e uma generalização mais poderosa denominada SPRP (Strong Probable Prime). Este é um teste que para um número inteiro N pode classificá-lo probabilisticamente como principal ou não, e testes repetidos podem aumentar a probabilidade de correção. A parte lenta do teste em si envolve principalmente a computação de um valor semelhante ao módulo A ^ (N-1) N. Qualquer pessoa que implemente variantes de criptografia de chave pública RSA utilizou esse algoritmo. É útil tanto para números inteiros enormes (como 512 bits) quanto para ints normais de 32 ou 64 bits.

O teste pode ser alterado de uma rejeição probabilística para uma prova definitiva de primalidade, pré-computando determinados parâmetros de entrada de teste que são conhecidos por sempre serem bem-sucedidos para faixas de N. Infelizmente, a descoberta desses "testes mais conhecidos" é efetivamente uma busca de um grande número ( de fato infinito). Em 1980, uma primeira lista de testes úteis foi criada por Carl Pomerance (famoso por ser o fator de fator RSA-129 com seu algoritmo Quadratic Seive.) Mais tarde, Jaeschke melhorou os resultados significativamente em 1993. Em 2004, Zhang e Tang aprimoraram a teoria e limites do domínio de pesquisa. Greathouse e Livingstone divulgaram os resultados mais modernos até agora na web, em http://math.crg4.com/primes.html , os melhores resultados de um enorme domínio de pesquisa.

Veja aqui para mais informações: http://primes.utm.edu/prove/prove2_3.html e http://forums.nvidia.com/index.php?showtopic=70483

Se você só precisa de uma maneira de gerar números primos muito grandes e não deseja gerar todos os números primos <um número inteiro n, pode usar o teste de Lucas-Lehmer para verificar os números primos de Mersenne. Um número primo de Mersenne está na forma de 2 ^ p -1. Penso que o teste de Lucas-Lehmer é o algoritmo mais rápido descoberto para os números primos de Mersenne.

E se você não apenas deseja usar o algoritmo mais rápido, mas também o hardware mais rápido, tente implementá-lo usando a Nvidia CUDA, escreva um kernel para CUDA e execute-o na GPU.

Você pode até ganhar algum dinheiro se descobrir números primos grandes o suficiente, a EFF está dando prêmios de US $ 50 mil a US $ 250 mil: https://www.eff.org/awards/coop

Há um teste matemático de 100% que verificará se um número Pé primo ou composto, chamado AKS Primality Test .

O conceito é simples: dado um número P, se todos os coeficientes de (x-1)^P - (x^P-1)são divisíveis por P, então Pé um número primo, caso contrário, é um número composto.

Por exemplo, dado P = 3, daria o polinômio:

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

E os coeficientes são divisíveis por 3, portanto, o número é primo.

E exemplo onde P = 4, que NÃO é um primo, renderia:

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

E aqui podemos ver que os coeficientes 6não são divisíveis por 4, portanto, NÃO são primos.

O polinômio (x-1)^Pserá P+1termos e pode ser encontrado usando a combinação. Portanto, esse teste será executado em O(n)tempo de execução, então não sei o quanto isso seria útil, pois você pode simplesmente percorrer ide 0 a 0 pe testar o restante.

O seu problema é decidir se um número específico é primo? Então você precisa de um teste de primalidade (fácil). Ou você precisa de todos os números primos até um determinado número? Nesse caso, as peneiras principais são boas (fáceis, mas requerem memória). Ou você precisa dos fatores primos de um número? Isso exigiria fatoração (difícil para grandes números, se você realmente deseja os métodos mais eficientes). Qual o tamanho dos números que você está vendo? 16 bits? 32 bits? Maior?

Uma maneira inteligente e eficiente é pré-calcular tabelas de números primos e mantê-las em um arquivo usando uma codificação em nível de bit. O arquivo é considerado um vetor de bit longo, enquanto o bit n representa o número inteiro n. Se n for primo, seu bit será definido como um e zero, caso contrário. A pesquisa é muito rápida (você calcula o deslocamento de bytes e uma máscara de bit) e não requer o carregamento do arquivo na memória.

Rabin-Miller é um teste probabilístico padrão de primalidade. (você executa K vezes e o número de entrada é definitivamente composto ou provavelmente é primo com probabilidade de erro 4- ^K . (algumas centenas de iterações e quase certamente está lhe dizendo a verdade)

Existe uma variante não probabilística (determinística) de Rabin Miller .

A Great Internet Mersenne Prime Search (GIMPS), que encontrou o recorde mundial de maior prime comprovado (2 ^74,207,281 - 1 em junho de 2017), usa vários algoritmos , mas estes são primos em formas especiais. No entanto, a página do GIMPS acima inclui alguns testes gerais de primalidade determinística. Eles parecem indicar que qual algoritmo é "mais rápido" depende do tamanho do número a ser testado. Se o seu número couber em 64 bits, provavelmente você não deve usar um método destinado a trabalhar com números primos de vários milhões de dígitos.

Depende da sua aplicação. Existem algumas considerações:

• Você precisa apenas das informações sobre se alguns números são primos, precisa de todos os números primos até um certo limite ou precisa (potencialmente) de todos os números primos?
• Qual é o tamanho dos números com os quais você precisa lidar?

Os testes de Miller-Rabin e analógicos são apenas mais rápidos do que uma peneira para números acima de um certo tamanho (algo em torno de alguns milhões, acredito). Abaixo disso, usar uma divisão de teste (se você tiver apenas alguns números) ou uma peneira é mais rápido.

Vou deixar você decidir se é o mais rápido ou não.

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

Demora aproximadamente 82 segundos para encontrar e imprimir números primos dentro de um intervalo de 1 a 1.000.000, no meu laptop Core 2 Duo com um processador de 2,40 GHz. E encontrou 78.498 números primos.

Eu sempre uso esse método para calcular números primos, seguindo o algoritmo de peneira.

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

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

Não conheço nenhum algoritmo predefinido, mas criei o meu, que é muito rápido. Pode processar números de 20 dígitos em menos de 1 segundos. A capacidade máxima deste programa é 18446744073709551615. O programa é:

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

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

Sei que é um pouco mais tarde, mas isso pode ser útil para as pessoas que chegam aqui a partir de pesquisas. De qualquer forma, aqui está um JavaScript que se baseia no fato de que apenas os fatores primos precisam ser testados; portanto, os primos anteriores gerados pelo código são reutilizados como fatores de teste para os posteriores. Obviamente, todos os valores pares e mod 5 são filtrados primeiro. O resultado estará na matriz P e esse código pode processar 10 milhões de números primos em menos de 1,5 segundos em um PC i7 (ou 100 milhões em cerca de 20). Reescrito em C, deve ser muito rápido.

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
}

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

    }
}