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

183

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!

Kasperasky
fonte
Um artigo velho que eu encontrei, mas parece interessante: Fun With Números Primos
Mvcoile
29
@Ajudem isso falha em números tão baixos quanto 7 (111). Também falha para 1001 = 9. E claramente falha em quase todos os números primos em geral (não abrange o caso 2 ^ p-1, que são números primos de Mersenne - exemplos gerados classicamente - que sempre terão a forma 111 ... 1)
Daniel Kats
1
@ Kasperasky - Você não mencionou qual peneira? Você provavelmente quer dizer Peneira de Eranthoses!
user2618142
Algoritmo de Peneira de Eratóstenes
Emad Aghayi

Respostas:

79

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.

Greg Hewgill
fonte
10
Na verdade, não acho que o primegen seja o mais rápido, ou mesmo o segundo mais rápido; yafu e primesieve são ambos mais rápidos em geral, eu acho, e certamente mais de 2 ^ 32. Ambas são peneiras (modificadas) de Eratóstenes, em vez da peneira de Atkin-Bernstein.
Charles
5
O Primesieve Sieve of Eratóstenes (SoE) é o algoritmo mais rápido possível e sempre será mais rápido do que qualquer implementação do Sieve of Atkin SoA, incluindo o de Bernstein como vinculado nesta resposta, porque o primesieve reduz o número de operações em comparação com o SoA: No intervalo de números de bits (2 ^ 32 - 1), o primesieve realiza cerca de 1,2 bilhão de abates, enquanto o SoA realiza um total de cerca de 1,4 bilhão de operações combinadas de alternância e sem quadrado, sendo ambas as operações da mesma complexidade e capazes de serem otimizadas da mesma maneira. maneira.
GordonBGood
7
Continuação: Bernstein apenas comparou o SoE usando a mesma fatoração efetiva da roda do SoA, que é uma roda 2; 3; 5, cuja roda resulta em cerca de 1,83 bilhão de abates na faixa de números de 32 bits; isso torna o SoA cerca de 30% mais rápido ao comparar esta versão restrita do SoE para outras otimizações equivalentes. No entanto, o algoritmo primesieve usa uma roda 2; 3; 5; 7 em combinação com uma roda 2; 3; 5; 7; 11; 13; 17 pré-abate de segmento de roda para reduzir o número de operações para cerca de 1,2 bilhão para rodar cerca de 16,7% mais rápido que o SoA com otimizações de loop de operação equivalentes.
precisa saber é o seguinte
6
Continuação2: O SoA não possui uma fatoração mais alta da roda fatorial usada para fazer muita diferença, pois a roda de fatoração 2; 3; 5 é uma parte "embutida" do algoritmo.
GordonBGood
4
@Eamon Nerbonne, WP está correto; no entanto, apenas ter uma complexidade computacional um pouco melhor não gera algoritmos mais rápidos para uso geral. Nesses comentários, refiro-me à fatoração máxima de roda da Peneira de Eratóstenes (SoE) (que não é possível para a Peneira de Atkin-SoA) gera um pouco menos de operações para a SoE até um alcance de cerca de um bilhão. Muito acima desse ponto, geralmente é necessário usar a segmentação de página para superar as limitações de memória, e é aí que o SoA falha, consumindo quantidades cada vez maiores de sobrecarga constante com alcance crescente.
precisa saber é o seguinte
29

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.

Georg Schölly
fonte
2
Uma lista de todos os números primos? Eu acho que você quer dizer uma lista dos primeiros números primos ... :)
j_random_hacker
9
Se você chamar 100000000 alguns, então sim. :)
Georg Schölly 18/01/09
58
certamente 100000000 é "um pouco" em comparação com o infinito;)
Timofey
9
Por que você acha que a peneira de Atkin (SoA) é mais rápida que a peneira de Eratóstenes (SoE)? Certamente não é quando se apenas implementa um programa usando o pseudo-código, como no artigo da Wikipedia que você vinculou. Se o SoE for implementado com um nível semelhante de possíveis otimizações usadas com o SoA, haverá um pouco menos operações para faixas de peneiras muito grandes para SoA do que para SoE, mas esse ganho é geralmente mais do que compensado pelo aumento da complexidade e pela fator extra constante adicional dessa complexidade computacional, de modo que, para aplicações práticas, o SoE seja melhor.
GordonBGood
26

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

Mack
fonte
17

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.

Kousha
fonte
5
O AKS é um método muito lento na prática, não competitivo com outros métodos conhecidos. O método que você descreve não é o AKS, mas um lema inicial mais lento que a divisão de teste não otimizada (como você indica).
DanaJ
Olá @Kousha, o que xsignifica? no (x-1)^P - (x^P-1). você tem um código de exemplo para isso? em C ++ para determinar se o número inteiro é primo ou não?
KiLLua
@kiLLua X é apenas uma variável. É o coeficiente de X que determina se o número é primo ou não. E não, eu não tenho o código. Não recomendo usar esse método para determinar se um número é primo ou não. Este é apenas um comportamento matemático muito legal dos números primos, mas, caso contrário, é incrivelmente ineficiente.
Kousha
5

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.

Christian Lindig
fonte
Um bom teste de primalidade é competitivo com a latência da memória principal para tabelas principais que poderiam caber razoavelmente, então eu não usaria isso a menos que pudesse caber no L2.
Charles
3

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.

Jason S
fonte
2

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.

Svante
fonte
0

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.

Tayyab Mazhar
fonte
3
isso é muito lento. o problema é i <= (ToCheck / 3). deveria ser i <= (ToCheck / i). com ele, ele pode ser executado em 0,1 segundos.
Will Ness
-1

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);
 }
Osman Goni Nahid
fonte
-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
fonte
r é usado antes da inicialização
zumalifeguard
-3

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;
}
Sushant
fonte
-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;
}
vidura
fonte
12
isso deve ser uma resposta em "Como escrever código não estruturado sem realmente usar o GOTO". Toda essa confusão apenas para codificar uma simples divisão de testes! (n%2)+1+(3*n)é meio que legal. :)
Will Ness
1
@ Will Ness, eu teria votado contra isso como resposta a essa pergunta; por que usar um loop for quando uma macro fará? :)
Rob Grant
-4

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
}
Robin Nixon
fonte
2
Isto lhe dará muitos problemas se você estiver gerando um grande número de primos, e para os comparations, melhor aproveitamento P [j] * P [j] <= k, porque sqrt é bastante lento
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
fonte
60
isso é o mais lento que você pode fazer.
Will Ness
1
Isso é muito lento, se o limite superior for digamos 10000000, esse código consumirá muito tempo !!
Dixit Singla
esse código é O (N ^ 2 / log N). sem break;ele seria ainda mais lento, O (N ^ 2), mas isso já poderia ser visto como um erro de codificação. salvar e testar por números primos é O (N ^ 2 / (log N) ^ 2), e o teste por números primos abaixo apenas da raiz quadrada do número é O (N ^ 1,5 / (log N) ^ 2).
Will Ness
@ WillNess Talvez um pouco hiperbólico. Ele poderia facilmente iniciar o loop for de 1 em vez de 2 e adicionar um j <= i em vez de j <i. :)
Kenny Cason
3
Não acho que este post deva ser excluído, ele serve como um contra-exemplo valioso.
Will Ness