Le code le plus efficace pour les 10000 premiers nombres premiers ?

Question

Je veux imprimer les 10000 premiers nombres premiers. Quelqu'un peut-il me donner le code le plus efficace pour cela ? Clarifications :

1. Il importe peu que votre code soit inefficace pour n >10000.
2. La taille du code n'a pas d'importance.
3. Vous ne pouvez pas simplement coder les valeurs en dur de quelque manière que ce soit.

Answer 1

Le tamis d'Atkin est probablement ce que vous recherchez, sa limite supérieure de temps d'exécution est O(N/log log N).

Si vous n'utilisez que les nombres supérieurs et inférieurs de 1 aux multiples de 6, cela pourrait être encore plus rapide, car tous les nombres premiers supérieurs à 3 sont éloignés de 1 d'un multiple de 6. Ressource pour ma déclaration

Answer 2

Je recommande un tamis, soit le Le tamis d'Eratosthène ou le Tamis d'Atkin.

Le crible d'Eratosthène est probablement la méthode la plus intuitive pour trouver une liste de nombres premiers. En gros, vous :

1. Écrivez une liste de nombres de 2 à la limite de votre choix, disons 1000.
2. Prenez le premier nombre qui n'est pas barré (pour la première itération, c'est 2) et rayez tous les multiples de ce nombre de la liste.
3. Répétez l'étape 2 jusqu'à ce que vous atteigniez la fin de la liste. Tous les nombres qui ne sont pas barrés sont premiers.

Il est évident qu'il existe de nombreuses optimisations possibles pour rendre cet algorithme plus rapide, mais c'est l'idée de base.

Le tamis d'Atkin utilise une approche similaire, mais malheureusement je n'en sais pas assez pour vous l'expliquer. Mais je sais que l'algorithme que j'ai lié prend 8 secondes pour calculer tous les nombres premiers jusqu'à 1000000000 sur un ancien Pentium II-350.

Code source du tamis d'Eratosthène : http://web.archive.org/web/20140705111241/http://primes.utm.edu/links/programs/sieves/Eratosthenes/C_source_code/

Tamis du code source d'Atkin : http://cr.yp.to/primegen.html

Answer 3

Ce n'est pas strictement contre la restriction du codage en dur, mais cela s'en rapproche terriblement. Pourquoi ne pas télécharger cette liste par programme et l'imprimer à la place ?

http://primes.utm.edu/lists/small/10000.txt

Answer 4

GateKiller pourquoi ne pas ajouter un break à cela if dans le foreach boucle ? Cela accélérerait les choses beaucoup parce que si, par exemple, 6 est divisible par 2, il n'est pas nécessaire de vérifier avec 3 et 5 (je voterais quand même pour votre solution si j'avais assez de réputation :-) ...).

ArrayList primeNumbers = new ArrayList();

for(int i = 2; primeNumbers.Count < 10000; i++) {
    bool divisible = false;

    foreach(int number in primeNumbers) {
        if(i % number == 0) {
            divisible = true;
            break;
        }
    }

    if(divisible == false) {
        primeNumbers.Add(i);
        Console.Write(i + " ");
    }
}

Answer 5

@Matt : log(log(10000)) est ~2

Extrait de l'article de wikipedia (que vous avez cité) Tamis d'Atkin :

Ce tamis calcule les nombres premiers jusqu'à N en utilisant O(N/log log N) opérations avec seulement N 1/2+o(1) bits de mémoire. C'est un peu mieux que le tamis d Eratosthène qui utilise O(N) et O(N 1/2 (log log N)/log N) bits de mémoire (A.O.L. Atkin, D.J. Bernstein, 2004) . Ces complexités asymptotiques computationnelles comprennent des optimisations simples, comme la roue factorisation, et la division du calcul à des blocs plus petits.

Étant donné les complexités asymptotiques de calcul le long de O(N) (pour Eratosthenes) et O(N/log(log(N))) (pour Atkin) on ne peut pas dire (pour les petits N=10_000 ) quel algorithme, s'il est mis en œuvre, sera le plus rapide.

Achim Flammenkamp a écrit dans Le tamis d'Eratosthène :

cité par :

@num1

Pour les intervalles supérieurs à 10^9, sûrement pour ceux > 10^10, le crible d' Eratosthenes est surpassé par le crible d'Atkins et Bernstein qui utilise des formes quadratiques binaires irréductibles irréductibles. Voir leur article pour le contexte informations de base ainsi que le paragraphe 5 de W. Galway pour le paragraphe 5 de sa thèse de doctorat.

Par conséquent, pour 10_000 Le tamis d'Eratosthenes peut être plus rapide que le tamis d'Atkin.

Pour répondre à OP, le code est prime_sieve.c (cité par num1 )