performance - trouver - pourquoi 1 n'est pas un nombre premier




Le code le plus efficace pour les 10000 premiers nombres premiers? (20)

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

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

C'est une vieille question, mais il y a quelque chose ici qui manque à tout le monde ...

Pour les nombres premiers aussi petits, la division d’essai n’est pas si lente… il n’ya que 25 nombres premiers inférieurs à 100. Avec si peu de nombres premiers à tester et de si petits nombres premiers, nous pouvons nous en sortir!

Si a est coprime à b, alors gcd ab = 1. Coprime. Mot amusant. Cela signifie qu'il ne partage pas les facteurs premiers . Nous pouvons donc tester la divisibilité par plusieurs nombres premiers avec un seul appel GCD. Combien? Eh bien, le produit des 15 premiers nombres premiers est inférieur à 2 ^ 64. Et le produit des 10 prochains est également inférieur à 2 ^ 64. C'est tout ce dont nous avons besoin. Mais est-ce que ça en vaut la peine?

Voyons voir:

check x = null $ filter ((==0) . (x `mod`)) $ [<primes up to 101>]
Prelude> length $ filter check [101,103..85600]
>>> 9975
(0.30 secs, 125,865,152 bytes

a = 16294579238595022365 :: Word64
b = 14290787196698157718
pre = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
primes = (pre ++) $ filter ((==1) . gcd a) $ filter ((==1) . gcd b) [99,101..85600]
main = print $ length primes

Prelude> main
>>> 10000
(0.05 secs, 36,387,520 bytes)

Une amélioration de 6 fois là-bas.

( length consiste à forcer le calcul de la liste. Par défaut, Haskell imprime 1 caractère Unicode à la fois. Ainsi, l' impression de la liste dominera le temps ou dominera la quantité de code réellement utilisée.)

Bien sûr, cela fonctionne dans GHCi - un code interprété en cours de réplication - sur un vieil ordinateur portable et aucun de ces numéros n’est interprété comme int64 s ou même BigInt s, et même si vous le demandez (eh bien, vous pouvez le forcer. , mais c’est moche et n’aide pas vraiment). Il interprète chaque numéro comme des éléments généralisés de type Integer pouvant être spécialisés dans un type particulier via la recherche par dictionnaire, et parcourant une liste chaînée (ce qui n'est pas fusionné ici car il n'est pas compilé). Fait intéressant, la fusion manuelle des deux filtres le ralentit réellement dans le REPL.

Compilons-le:

...\Haskell\8.6\Testbed>Primes.exe +RTS -s
10000
606,280 bytes allocated in the heap
Total   time    0.000s  (  0.004s elapsed)

Utilisation du rapport RTS parce que Windows. Certaines lignes ont été ajustées car elles ne sont pas pertinentes - il s’agissait d’autres données GC, ou de mesures d’une partie seulement de l’exécution, et leur totalisation s’élève à 0,004 (ou moins). Ce n'est pas non plus un pliage constant, car Haskell n'en fait pas beaucoup. Si nous nous plions constamment ( main = print 10000 ), l'allocation est considérablement réduite:

...Haskell\8.6\Testbed>Primes.exe +RTS -s
10000
47,688 bytes allocated in the heap
Total   time    0.000s  (  0.001s elapsed)

Littéralement, juste assez pour charger le runtime, puis découvrez qu'il n'y a rien d'autre à faire que d'imprimer un nombre et de sortir. Ajoutons la factorisation de roue:

wheel = scanl (+) 7 $ cycle [4, 2, 4, 2, 4, 6, 2, 6]
primes = (pre ++) $ filter ((==1) . gcd a) $ filter ((==1) . gcd b) $ takeWhile (<85600) wheel

Total   time    0.000s  (  0.003s elapsed)

Réduit environ 1/3 par rapport à notre référence de main = print 10000 , mais il y a certainement de la place pour plus d'optimisation. En fait, par exemple, il n’a plus été utilisé pour effectuer un GC, alors qu’il ne devrait pas y avoir d’utilisation de tas. Pour une raison quelconque, la compilation pour le profilage ici réduit en fait le temps d'exécution à 2 millisecondes:

Tue Nov 12 21:13 2019 Time and Allocation Profiling Report  (Final)

   Primes.exe +RTS -p -RTS

total time  =        0.00 secs   (2 ticks @ 1000 us, 1 processor)
total alloc =     967,120 bytes  (excludes profiling overheads)

Je vais laisser cela tel quel pour le moment, je suis à peu près sûr que la gigue aléatoire commence à dominer.


En utilisant Sieve of Eratosthenes, le calcul est assez rapide comparé à l'algorithme de nombres premiers "connu".

En utilisant le pseudocode de son wiki ( https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes ), je peux avoir la solution en C #.

/// Get non-negative prime numbers until n using Sieve of Eratosthenes.
public int[] GetPrimes(int n) {
    if (n <= 1) {
        return new int[] { };
    }

    var mark = new bool[n];
    for(var i = 2; i < n; i++) {
        mark[i] = true;
    }

    for (var i = 2; i < Math.Sqrt(n); i++) {
        if (mark[i]) {
            for (var j = (i * i); j < n; j += i) {
                mark[j] = false;
            }
        }
    }

    var primes = new List<int>();
    for(var i = 3; i < n; i++) {
        if (mark[i]) {
            primes.Add(i);
        }
    }

    return primes.ToArray();
}

GetPrimes (100000000) prend 2s et 330ms.

REMARQUE : La valeur peut varier en fonction des spécifications matérielles.


Je passe un peu de temps à écrire un programme qui calcule beaucoup de nombres premiers et c’est le code que j’utilise pour calculer un fichier texte contenant les 1.000.000.000 premiers nombres premiers. C'est en allemand, mais la partie intéressante est la méthode calcPrimes() . Les nombres premiers sont stockés dans un tableau appelé Primzahlen. Je recommande un processeur 64 bits car les calculs sont faits avec des entiers 64 bits.

import java.io.*;
class Primzahlengenerator {
    long[] Primzahlen;
    int LastUnknown = 2;
    public static void main(String[] args)  {
        Primzahlengenerator Generator = new Primzahlengenerator();
        switch(args.length) {
            case 0:  //Wenn keine Argumente übergeben worden:
                Generator.printHelp(); //Hilfe ausgeben
                return; //Durchfallen verhindern
            case 1:
                try {
                    Generator.Primzahlen = new long[Integer.decode(args[0]).intValue()];
                }
                catch (NumberFormatException e) {
                    System.out.println("Das erste Argument muss eine Zahl sein, und nicht als Wort z.B. \"Tausend\", sondern in Ziffern z.B. \"1000\" ausgedrückt werden.");//Hinweis, wie man die Argumente angeben muss ausgeben
                    Generator.printHelp();                    //Generelle Hilfe ausgeben
                    return;
                }
                break;//dutchfallen verhindern

            case 2:
                switch (args[1]) {
                    case "-l":
                        System.out.println("Sie müsen auch eine Datei angeben!"); //Hilfemitteilung ausgeben
                        Generator.printHelp();                                    //Generelle Hilfe ausgeben
                        return;
                }
                break;//durchfallen verhindern
            case 3:
                try {
                    Generator.Primzahlen = new long[Integer.decode(args[0]).intValue()];
                }
                catch (NumberFormatException e) {
                    System.out.println("Das erste Argument muss eine Zahl sein, und nicht als Wort z.B. \"Tausend\", sondern in Ziffern z.B. \"1000\" ausgedrückt werden.");//Hinweis, wie man die Argumente angeben muss ausgeben
                    Generator.printHelp();                      //Generelle Hilfe ausgeben
                    return;
                }
                switch(args[1]) {
                    case "-l":
                        Generator.loadFromFile(args[2]);//Datei Namens des Inhalts von Argument 3 lesen, falls Argument 2 = "-l" ist
                        break;
                    default:
                        Generator.printHelp();
                        break;
                }
                break;
            default:
                Generator.printHelp();
                return;
        }
        Generator.calcPrims();
    }
    void printHelp() {
        System.out.println("Sie müssen als erstes Argument angeben, die wieviel ersten Primzahlen sie berechnen wollen.");   //Anleitung wie man das Programm mit Argumenten füttern muss
        System.out.println("Als zweites Argument können sie \"-l\" wählen, worauf die Datei, aus der die Primzahlen geladen werden sollen,");
        System.out.println("folgen muss. Sie muss genauso aufgebaut sein, wie eine Datei Primzahlen.txt, die durch den Aufruf \"java Primzahlengenerator 1000 > Primzahlen.txt\" entsteht.");
    }
    void loadFromFile(String File) {
        // System.out.println("Lese Datei namens: \"" + File + "\"");
        try{
            int x = 0;
            BufferedReader in = new BufferedReader(new FileReader(File));
            String line;
            while((line = in.readLine()) != null) {
                Primzahlen[x] = new Long(line).longValue();
                x++;
            }
            LastUnknown = x;
        } catch(FileNotFoundException ex) {
            System.out.println("Die angegebene Datei existiert nicht. Bitte geben sie eine existierende Datei an.");
        } catch(IOException ex) {
            System.err.println(ex);
        } catch(ArrayIndexOutOfBoundsException ex) {
            System.out.println("Die Datei enthält mehr Primzahlen als der reservierte Speicherbereich aufnehmen kann. Bitte geben sie als erstes Argument eine größere Zahl an,");
            System.out.println("damit alle in der Datei enthaltenen Primzahlen aufgenommen werden können.");
            }
        /* for(long prim : Primzahlen) {
            System.out.println("" + prim);
        } */
        //Hier soll code stehen, der von der Datei mit angegebenem Namen ( Wie diese aussieht einfach durch angeben von folgendem in cmd rausfinden:
        //java Primzahlengenerator 1000 > 1000Primzahlen.txt
        //da kommt ne textdatei, die die primzahlen enthält. mit Long.decode(String ziffern).longValue();
        //erhält man das was an der entsprechenden stelle in das array soll. die erste zeile soll in [0] , die zweite zeile in [1] und so weiter.
        //falls im arry der platz aus geht(die exception kenn ich grad nich, aber mach mal:
        //int[] foo = { 1, 2, 3};
        //int bar = foo[4];
        //dann kriegst ne exception, das ist die gleiche die man kriegt, wenn im arry der platzt aus geht.
    }
    void calcPrims() {
        int PrimzahlNummer = LastUnknown;
        // System.out.println("LAstUnknown ist: " + LastUnknown);
        Primzahlen[0] = 2;
        Primzahlen[1] = 3;
        long AktuelleZahl = Primzahlen[PrimzahlNummer - 1];
        boolean IstPrimzahl;
        // System.out.println("2");
        // System.out.println("3");
        int Limit = Primzahlen.length;
        while(PrimzahlNummer < Limit) {
            IstPrimzahl = true;
            double WurzelDerAktuellenZahl = java.lang.Math.sqrt(AktuelleZahl);
            for(int i = 1;i < PrimzahlNummer;i++) {
                if(AktuelleZahl % Primzahlen[i] == 0) {
                    IstPrimzahl = false;
                    break;
                }
                if(Primzahlen[i] > WurzelDerAktuellenZahl) break;
            }
            if(IstPrimzahl) {
                Primzahlen[PrimzahlNummer] = AktuelleZahl;
                PrimzahlNummer++;
                // System.out.println("" + AktuelleZahl);
            }
            AktuelleZahl = AktuelleZahl + 2;
        }
        for(long prim : Primzahlen) {
            System.out.println("" + prim);
        }
    }
}

Je peux vous donner quelques conseils, vous devez le mettre en œuvre.

  1. Pour chaque nombre, obtenez la moitié de ce nombre. Par exemple, pour le contrôle 21, n’obtenez le reste qu’en le divisant entre 2 et 10.
  2. Si c'est un nombre impair, ne divisez que par un nombre impair, et vice versa. Comme pour 21, divisez avec 3, 5, 7, 9 seulement.

Méthode la plus efficace à laquelle je me suis habitué jusqu'à présent.


Puisque vous voulez seulement 10000 premiers nombres premiers, plutôt que de coder un algorithme complexe, je vous suggère ce qui suit

boolean isPrime(int n){
//even but is prime
    if(n==2)
        return true;
//even numbers filtered already 
    if(n==0 || n==1 || n%2==0)
        return false;

// loop for checking only odd factors
// i*i <= n  (same as i<=sqrt(n), avoiding floating point calculations)
    for(int i=3 ; i*i <=n ; i+=2){
    // if any odd factor divides n then its not a prime!
        if(n%i==0)
            return false;
    }
// its prime now
    return true;
}

maintenant appeler est premier comme vous en avez besoin

for(int i=1 ; i<=1000 ; i++){
    if(isPrime(i)){
       //do something
    }
}

Utilisation de la méthode Array.prototype.find () en Javascript. 2214,486 ms

function isPrime (number) {

  function prime(element) {
    let start = 2;
    while (start <= Math.sqrt(element)) {
      if (element % start++ < 1) {
        return false;
      }
    }
    return element > 1;
  }

  return [number].find(prime)

}

function logPrimes (n) {

  let count = 0
  let nth = n

  let i = 0
  while (count < nth) {
    if (isPrime(i)) {
      count++
      console.log('i', i) //NOTE: If this line is ommited time to find 10,000th prime is 121.157ms
      if (count === nth) {
        console.log('while i', i)
        console.log('count', count)
      }
    }
    i++
  }

}

console.time(logPrimes)

logPrimes(10000)

console.timeEnd(logPrimes) // 2214.486ms

Voici mon code qui trouve les premiers 10 000 nombres premiers en 0,049655 seconde sur mon ordinateur portable, les premiers 1 000 000 en moins de 6 secondes et les 2 000 000 premiers en 15 secondes.
Une petite explication. Cette méthode utilise 2 techniques pour trouver le nombre premier

  1. Tout d’abord, tout nombre non premier est composé de multiples de nombres premiers. Ce code teste donc en divisant le nombre de test par des nombres premiers plus petits au lieu de tout autre nombre, ce qui diminue le calcul d’au moins 10 fois pour un nombre à 4 chiffres et encore plus pour un plus grand nombre
  2. deuxièmement, en plus de diviser par le nombre premier, il ne divise que les nombres premiers plus petits ou égaux à la racine du nombre testé, ce qui réduit considérablement les calculs; cela fonctionne car tout nombre supérieur à la racine du nombre aura un numéro de contrepartie qui doit être plus petit que la racine du nombre, mais puisque nous avons déjà testé tous les nombres plus petits que la racine, nous n’avons donc pas besoin de nous préoccuper d’un nombre supérieur à la racine du nombre testé.

Exemple de sortie pour le premier 10 000 nombre premier
https://drive.google.com/open?id=0B2QYXBiLI-lZMUpCNFhZeUphck0 https://drive.google.com/open?id=0B2QYXBiLI-lZbmRtTkZETnp6Ykk

Voici le code en langage C, entrez 1 puis 10 000 pour imprimer les 10 000 premiers nombres premiers.
Edit: j’ai oublié que cela contient une bibliothèque mathématique. Si vous utilisez Windows ou Visual Studio, cela devrait être correct, mais sous Linux, vous devez compiler le code en utilisant l’argument -lm ou le code risque de ne pas fonctionner.
Exemple: gcc -Wall -o "% e ""% f "-lm

#include <stdio.h>
#include <math.h>
#include <time.h>
#include <limits.h>

/* Finding prime numbers */
int main()
{   
    //pre-phase
    char d,w;
    int l,o;
    printf("  1. Find first n number of prime numbers or Find all prime numbers smaller than n ?\n"); // this question helps in setting the limits on m or n value i.e l or o 
    printf("     Enter 1 or 2 to get anwser of first or second question\n");
    // decision making
    do
    {
        printf("  -->");
        scanf("%c",&d);
        while ((w=getchar()) != '\n' && w != EOF);
        if ( d == '1')
        {
            printf("\n  2. Enter the target no. of primes you will like to find from 3 to 2,000,000 range\n  -->");
            scanf("%10d",&l);
            o=INT_MAX;
            printf("  Here we go!\n\n");
            break;
        }
        else if ( d == '2' )
        {
            printf("\n  2.Enter the limit under which to find prime numbers from 5 to 2,000,000 range\n  -->");
            scanf("%10d",&o);
            l=o/log(o)*1.25;
            printf("  Here we go!\n\n");
            break;
        }
        else printf("\n  Try again\n");
    }while ( d != '1' || d != '2' );

    clock_t start, end;
    double cpu_time_used;
    start = clock(); /* starting the clock for time keeping */

    // main program starts here
    int i,j,c,m,n; /* i ,j , c and m are all prime array 'p' variables and n is the number that is being tested */
    int s,x;

    int p[ l ]; /* p is the array for storing prime numbers and l sets the array size, l was initialized in pre-phase */
    p[1]=2;
    p[2]=3;
    p[3]=5;
    printf("%10dst:%10d\n%10dnd:%10d\n%10drd:%10d\n",1,p[1],2,p[2],3,p[3]); // first three prime are set
    for ( i=4;i<=l;++i ) /* this loop sets all the prime numbers greater than 5 in the p array to 0 */
        p[i]=0;

    n=6; /* prime number testing begins with number 6 but this can lowered if you wish but you must remember to update other variables too */
    s=sqrt(n); /* 's' does two things it stores the root value so that program does not have to calaculate it again and again and also it stores it in integer form instead of float*/
    x=2; /* 'x' is the biggest prime number that is smaller or equal to root of the number 'n' being tested */

    /* j ,x and c are related in this way, p[j] <= prime number x <= p[c] */

    // the main loop begins here
    for ( m=4,j=1,c=2; m<=l && n <= o;)
    /* this condition checks if all the first 'l' numbers of primes are found or n does not exceed the set limit o */
    {
            // this will divide n by prime number in p[j] and tries to rule out non-primes
            if ( n%p[j]==0 )
            {
                /* these steps execute if the number n is found to be non-prime */

                ++n; /* this increases n by 1 and therefore sets the next number 'n' to be tested */
                s=sqrt(n); /* this calaulates and stores in 's' the new root of number 'n' */
                if ( p[c] <= s && p[c] != x ) /* 'The Magic Setting' tests the next prime number candidate p[c] and if passed it updates the prime number x */
                {
                    x=p[c];
                    ++c;
                }
                j=1;
                /* these steps sets the next number n to be tested and finds the next prime number x if possible for the new number 'n' and also resets j to 1 for the new cycle */
                continue; /* and this restarts the loop for the new cycle */
            }
            // confirmation test for the prime number candidate n
            else if ( n%p[j]!=0 && p[j]==x )
            {
                /* these steps execute if the number is found to be prime */
                p[m]=n;
                printf("%10dth:%10d\n",m,p[m]);
                ++n;
                s = sqrt(n);
                ++m;
                j=1;
                /* these steps stores and prints the new prime number and moves the 'm' counter up and also sets the next number n to be tested and also resets j to 1 for the new cycle */
                continue; /* and this restarts the loop */
                /* the next number which will be a even and non-prime will trigger the magic setting in the next cycle and therfore we do not have to add another magic setting here*/
            }
            ++j; /* increases p[j] to next prime number in the array for the next cycle testing of the number 'n' */
            // if the cycle reaches this point that means the number 'n' was neither divisible by p[j] nor was it a prime number
            // and therfore it will test the same number 'n' again in the next cycle with a bigger prime number
    }
    // the loops ends
    printf("  All done !!\n");
    end = clock();
    cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
    printf("  Time taken : %lf sec\n",cpu_time_used);
}

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

De l'article de Wikipédia (que vous avez cité) Sieve of Atkin :

Ce tamis calcule les nombres premiers jusqu’à N en utilisant O(N/log log N) avec seulement N 1/2 + o (1) bits de mémoire. C'est un peu mieux que le tamis d'Eratosthenes qui utilise les opérations O(N) et les bits de mémoire O (N 1/2 (log log N) / log N) (AOL Atkin, DJ Bernstein, 2004) . Ces complexités de calcul asymptotiques incluent des optimisations simples, telles que la factorisation par roue, et le fractionnement du calcul en blocs plus petits.

Étant donné les complexités de calcul asymptotiques le long de O(N) (pour Eratosthenes) et de O(N/log(log(N))) (pour Atkin), nous ne pouvons pas dire (pour un petit N=10_000 ) quel algorithme mis en oeuvre sera plus rapide.

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

cité par:

@ num1

Pour des intervalles plus grands d’environ 10 ^ 9, sûrement pour ceux> 10 ^ 10, le tamis d’Ératosthène est surperformé par le tamis d’Atkins et de Bernstein qui utilise des formes quadratiques binaires irréductibles. Voir leur document pour des informations générales ainsi que le paragraphe 5 du doctorat de W. Galway. thèse.

Donc, pour 10_000 tamis d'Eratosthenes peut être plus rapide que tamis d'Atkin.

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


En Haskell, nous pouvons écrire presque mot pour mot la définition mathématique du tamis d’Ératosthène, "les nombres premiers sont des nombres naturels supérieurs à 1 sans nombres composites, où les composites sont trouvés par énumération des multiples de chaque nombre premier ":

import Data.List.Ordered (minus, union)

primes = 2 : minus [3..] (foldr (\p r -> p*p : union [p*p+p, p*p+2*p..] r)
                                [] primes)

primes !! 10000 primes !! 10000 est quasi instantanée.

Les références:

Le code ci-dessus est facilement modifié pour travailler uniquement sur les cotes, primes = 2 : 3 : minus [5,7..] (foldr (\pr -> p*p : union [p*p+2*p, p*p+4*p..] r) [] (tail primes)) . La complexité temporelle est considérablement améliorée (jusqu'à un facteur de log supérieur à celui optimal) en se pliant en une structure arborescente, et la complexité spatiale est considérablement améliorée par la production de nombres premiers à plusieurs étages ,

primes = 2 : _Y ( (3:) . sieve 5 . _U . map (\p -> [p*p, p*p+2*p..]) )
  where
    _Y g = g (_Y g)                        -- non-sharing fixpoint combinator
    _U ((x:xs):t) = x : (union xs . _U . pairs) t       -- ~= nub.sort.concat
    pairs    (xs:ys:t)  = union xs ys : pairs t
    sieve k s@(x:xs) | k < x      = k : sieve (k+2) s   -- ~= [k,k+2..]\\s,
                     | otherwise  =     sieve (k+2) xs  --   when s⊂[k,k+2..]

(Dans Haskell, les parenthèses sont utilisées pour le regroupement, un appel de fonction est indiqué simplement par juxtaposition, (:) est un opérateur de contre-listes, et (.) Est un opérateur de composition fonctionnel: (f . g) x = (\y -> f (gy)) x = f (gx) ).


En python

import gmpy
p=1
for i in range(10000):
    p=gmpy.next_prime(p)
    print p 

En utilisant GMP, on pourrait écrire ce qui suit:

#include <stdio.h>
#include <gmp.h>

int main() {
  mpz_t prime;
  mpz_init(prime);
  mpz_set_ui(prime, 1);
  int i;
  char* num = malloc(4000);
  for(i=0; i<10000; i++) {
    mpz_nextprime(prime, prime);
    printf("%s, ", mpz_get_str(NULL,10,prime));
  }
}

Sur mon Macbook Pro à 2,33 GHz, il s'exécute comme suit:

time ./a.out > /dev/null

real    0m0.033s
user    0m0.029s
sys    0m0.003s

Calcul de 1 000 000 de nombres premiers sur le même ordinateur portable:

time ./a.out > /dev/null

real    0m14.824s
user    0m14.606s
sys     0m0.086s

GMP est hautement optimisé pour ce genre de chose. Sauf si vous voulez vraiment comprendre les algorithmes en écrivant les vôtres, il vous sera conseillé d'utiliser libGMP sous C.


J'ai adapté le code présent sur CodeProject pour créer les éléments suivants:

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

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

Tester ceci sur mon serveur ASP.NET prenait environ 1 minute à courir.


L' algorithme de tamisage parque mentionné par BenGoldberg mérite un examen plus approfondi, non seulement parce qu'il est très élégant, mais aussi parce qu'il peut parfois être utile dans la pratique (contrairement au tamis d'Atkin, qui est un exercice purement académique).

L’idée de base de l’algorithme de tamis deque consiste à utiliser un tamis coulissant, suffisamment grand pour contenir au moins un multiple distinct pour chacun des facteurs premiers «actifs» - c’est-à-dire les nombres premiers dont le carré ne dépasse pas le nombre le plus bas. actuellement représenté par le tamis en mouvement. Une autre différence par rapport au SoE est que le tamis de deque stocke les facteurs réels dans les emplacements des composites, pas les booléens.

L'algorithme étend la taille de la fenêtre du tamis selon les besoins, ce qui permet d'obtenir des performances relativement homogènes sur une large plage jusqu'à ce que le tamis dépasse sensiblement la capacité du cache L1 de la CPU. Le dernier nombre premier qui convient parfaitement est 25 237 523 (le nombre premier, 1 579 791), ce qui donne un chiffre approximatif approximatif pour la plage de fonctionnement raisonnable de l'algorithme.

L'algorithme est assez simple et robuste, et il offre même des performances sur une plage beaucoup plus large qu'un tamis non segmenté d'Eratosthenes. Ce dernier est beaucoup plus rapide tant que son tamis s’intègre parfaitement dans la mémoire cache, c’est-à-dire jusqu’à 2 ^ 16 pour un tamis à chances seulement avec des bools d’octets. Ensuite, ses performances chutent de plus en plus, même s’il reste toujours nettement plus rapide que le deque malgré le handicap (du moins dans les langages compilés comme C / C ++, Pascal ou Java / C #).

Voici un rendu de l'algorithme deque tieve en C #, car je trouve ce langage - malgré ses nombreuses failles - beaucoup plus pratique pour les algorithmes de prototypage et l'expérimentation que le C ++ extrêmement lourd et pédant. (Sidenote: J'utilise le LINQPad gratuit qui permet de plonger directement, sans tout le désordre lié à la configuration de projets, de makefiles, de répertoires ou autres, et qui me donne le même degré d'interactivité qu'un prompt python).

C # n'a pas de type deque explicite, mais la List<int> simple List<int> fonctionne assez bien pour démontrer l'algorithme.

Remarque: cette version n’utilise pas de deque pour les nombres premiers, car il n’a tout simplement pas de sens de supprimer sqrt (n) de n nombres premiers. A quoi servirait-il de supprimer 100 nombres premiers et de laisser 9900? Au moins, tous les nombres premiers sont rassemblés dans un vecteur net, prêt pour un traitement ultérieur.

static List<int> deque_sieve (int n = 10000)
{
    Trace.Assert(n >= 3);

    var primes = new List<int>()  {  2, 3  };
    var sieve = new List<int>()  {  0, 0, 0  };

    for (int sieve_base = 5, current_prime_index = 1, current_prime_squared = 9; ; )
    {
        int base_factor = sieve[0];

        if (base_factor != 0)
        {
            // the sieve base has a non-trivial factor - put that factor back into circulation
            mark_next_unmarked_multiple(sieve, base_factor);
        }
        else if (sieve_base < current_prime_squared)  // no non-trivial factor -> found a non-composite
        {
            primes.Add(sieve_base);

            if (primes.Count == n)
                return primes;
        }
        else // sieve_base == current_prime_squared
        {
            // bring the current prime into circulation by injecting it into the sieve ...
            mark_next_unmarked_multiple(sieve, primes[current_prime_index]);

            // ... and elect a new current prime
            current_prime_squared = square(primes[++current_prime_index]);
        }

        // slide the sieve one step forward
        sieve.RemoveAt(0);  sieve_base += 2;
    }
}

Voici les deux fonctions d'assistance:

static void mark_next_unmarked_multiple (List<int> sieve, int prime)
{
    int i = prime, e = sieve.Count;

    while (i < e && sieve[i] != 0)
        i += prime;

    for ( ; e <= i; ++e)  // no List<>.Resize()...
        sieve.Add(0);

    sieve[i] = prime;
}

static int square (int n)
{
    return n * n;
}

La meilleure façon de comprendre l’algorithme est probablement de l’imaginer comme un tamis d’ératosthène segmenté spécial avec une taille de segment de 1, accompagné d’une zone de débordement où les nombres premiers s’arrêtent lorsqu’ils filent à la fin du segment. Sauf que la seule cellule du segment (aka sieve[0] ) a déjà été tamisée lorsque nous y arrivons, car elle s'est écrasée alors qu'elle faisait partie de la zone de débordement.

Le nombre représenté par sieve[0] est conservé dans sieve_base , bien que sieve_front ou window_base soient également de bons noms permettant de tracer des parallèles avec le code de Ben ou avec les implémentations de tamis segmentés / fenêtrés.

Si sieve[0] contient une valeur non nulle, alors cette valeur est un facteur de sieve_base , qui peut donc être reconnu comme composite. Comme la cellule 0 est un multiple de ce facteur, il est facile de calculer son prochain bond, qui est simplement 0 plus ce facteur. Si cette cellule est déjà occupée par un autre facteur, nous ajoutons simplement le facteur à nouveau, et ainsi de suite jusqu'à trouver un multiple du facteur où aucun autre facteur n'est actuellement en attente (extension du tamis si nécessaire). Cela signifie également qu'il n'est pas nécessaire de stocker les décalages de travail actuels des différents nombres premiers d'un segment à l'autre, comme dans un tamis segmenté normal. Chaque fois que nous trouvons un facteur dans le sieve[0] , son décalage de travail actuel est 0.

Le nombre premier actuel entre en jeu de la manière suivante. Un nombre premier ne peut devenir courant qu'après sa propre occurrence dans le flux (c'est-à-dire qu'il a été détecté comme nombre premier car il n'est pas marqué par un facteur) et il restera actuel jusqu'au moment exact où le sieve[0] atteindra son carré. Tous les multiples inférieurs de ce nombre premier doivent avoir été radiés en raison des activités de nombres premiers plus petits, comme dans un SoE normal. Mais aucun des plus petits nombres premiers ne peut rayer du carré, car le seul facteur du carré est le premier lui-même et il n’est pas encore en circulation à ce stade. Cela explique les actions entreprises par l’algorithme dans le cas sieve_base == current_prime_squared (ce qui implique sieve[0] == 0 , en passant).

Le cas sieve[0] == 0 && sieve_base < current_prime_squared s’explique facilement: cela signifie que sieve_base ne peut pas être un multiple d’un nombre premier inférieur au nombre premier, sinon il aurait été marqué comme composite. Je ne peux pas non plus être un multiple supérieur du nombre premier actuel, car sa valeur est inférieure à la valeur carrée du nombre premier actuel. Par conséquent, il doit s'agir d'un nouveau premier.

L'algorithme est évidemment inspiré du tamis d'Eratosthène, mais il est également très différent. Le crible d’Ératosthène tire sa vitesse supérieure de la simplicité de ses opérations élémentaires: un seul ajout d’indice et un magasin pour chaque étape de l’opération est tout ce qu’il fait pendant de longues périodes.

Voici un tamis simple d’Eratosthenes, non segmenté, que j’utilise normalement pour tamiser les nombres premiers du facteur de tamisage, c’est-à-dire jusqu’à 2 ^ 16. Pour cet article, je l'ai modifié pour fonctionner au-delà de 2 ^ 16 en remplaçant int par ushort

static List<int> small_odd_primes_up_to (int n)
{
    var result = new List<int>();

    if (n < 3)
        return result;

    int sqrt_n_halved = (int)(Math.Sqrt(n) - 1) >> 1, max_bit = (n - 1) >> 1;
    var odd_composite = new bool[max_bit + 1];

    for (int i = 3 >> 1; i <= sqrt_n_halved; ++i)
        if (!odd_composite[i])
            for (int p = (i << 1) + 1, j = p * p >> 1; j <= max_bit; j += p)
                odd_composite[j] = true;

    result.Add(3);  // needs to be handled separately because of the mod 3 wheel

    // read out the sieved primes
    for (int i = 5 >> 1, d = 1; i <= max_bit; i += d, d ^= 3)
        if (!odd_composite[i])
            result.Add((i << 1) + 1);

    return result;
}

Lors du tamisage des 10000 premiers nombres premiers, un cache L1 typique de 32 Ko sera dépassé, mais la fonction reste très rapide (une fraction de milliseconde même en C #).

Si vous comparez ce code au tamis deque, il est facile de voir que les opérations du tamis de deque sont beaucoup plus compliquées, et il ne peut pas amortir efficacement ses frais généraux, car il effectue toujours le plus petit nombre possible de croisements consécutifs. (exactement un seul barrage, après avoir ignoré tous les multiples qui ont déjà été rayés).

Remarque: le code C # utilise int au lieu de uint car les compilateurs les plus récents ont l'habitude de générer du code non uint pour uint , probablement dans le but de pousser les gens vers des entiers signés ... Dans la version C ++ du code ci-dessus, j'ai utilisé unsigned partout, naturellement; le repère devait être en C ++ car je voulais qu'il soit basé sur un type deque supposé adéquat ( std::deque<unsigned> ; l'utilisation de unsigned short présentait aucun avantage en termes de performances. Voici les numéros pour mon ordinateur portable Haswell (VC ++ 2015 / x64):

deque vs simple: 1.802 ms vs 0.182 ms
deque vs simple: 1.836 ms vs 0.170 ms 
deque vs simple: 1.729 ms vs 0.173 ms

Remarque: les temps C # sont pratiquement le double du temps C ++, ce qui est plutôt bien pour C # et cela montre que List<int> n'est pas en reste, même s'il est abusé en tant que deque.

Le code de tamisage simple bloque toujours le coude hors de l'eau, même s'il fonctionne déjà au-delà de sa plage de fonctionnement normale (taille du cache L1 dépassée de 50%, avec écrasement du cache sous-jacent). La partie dominante ici est la lecture des nombres premiers tamisés, et cela n’est pas beaucoup affecté par le problème de cache. Dans tous les cas, la fonction a été conçue pour tamiser les facteurs de facteurs, c'est-à-dire le niveau 0 dans une hiérarchie de tamisage à 3 niveaux, et ne doit généralement renvoyer que quelques centaines de facteurs ou un faible nombre de milliers. D'où sa simplicité.

Les performances pourraient être améliorées de plus d'un ordre de grandeur en utilisant un tamis segmenté et en optimisant le code d'extraction des nombres premiers tamisés (mod 3 étalées et déroulées deux fois, ou mod 15 et une fois déroulées), mais des performances encore plus élevées pourraient être évincées. le code en utilisant une roue mod 16 ou 30 avec toutes les garnitures (c'est-à-dire le déroulement complet pour tous les résidus). Quelque chose comme cela est expliqué dans ma réponse à Trouver le nombre premier positionné par dessus Code Review, où un problème similaire a été discuté. Mais il est difficile de voir l'intérêt d'améliorer une fois de moins d'une milliseconde pour une tâche ponctuelle ...

Pour mettre les choses un peu en perspective, voici les timings C ++ permettant de tamiser jusqu'à 100 000 000:

deque vs simple: 1895.521 ms vs 432.763 ms
deque vs simple: 1847.594 ms vs 429.766 ms
deque vs simple: 1859.462 ms vs 430.625 ms

En revanche, un tamis segmenté en C # avec quelques cloches et sifflets fait le même travail en 95 ms (pas de minutage C ++ disponible, car je ne code que pour le moment en C #).

Les choses peuvent sembler radicalement différentes dans un langage interprété comme Python, où chaque opération a un coût élevé et où l'interpréteur annule toutes les différences dues aux branches prédites ou aux opérations imprévues (opérations décalées, ajouts) par rapport aux opérations multi-cycles (opérations de multiplication). et peut-être même la division). Cela risquerait de saper l’avantage en simplicité du tamis d’Ératosthène, ce qui pourrait rendre la solution de déque un peu plus attrayante.

En outre, de nombreux chronométrages rapportés par d'autres répondants dans cette rubrique sont probablement dominés par le temps de sortie . C'est une guerre totalement différente, où mon arme principale est une classe simple comme celle-ci:

class CCWriter
{
    const int SPACE_RESERVE = 11;  // UInt31 + '\n'

    public static System.IO.Stream BaseStream;
    static byte[] m_buffer = new byte[1 << 16];  // need 55k..60k for a maximum-size range
    static int m_write_pos = 0;
    public static long BytesWritten = 0;         // for statistics

    internal static ushort[] m_double_digit_lookup = create_double_digit_lookup();

    internal static ushort[] create_double_digit_lookup ()
    {
        var lookup = new ushort[100];

        for (int lo = 0; lo < 10; ++lo)
            for (int hi = 0; hi < 10; ++hi)
                lookup[hi * 10 + lo] = (ushort)(0x3030 + (hi << 8) + lo);

        return lookup;
    }

    public static void Flush ()
    {
        if (BaseStream != null && m_write_pos > 0)
            BaseStream.Write(m_buffer, 0, m_write_pos);

        BytesWritten += m_write_pos;
        m_write_pos = 0;
    }

    public static void WriteLine ()
    {
        if (m_buffer.Length - m_write_pos < 1)
            Flush();

        m_buffer[m_write_pos++] = (byte)'\n';
    }

    public static void WriteLinesSorted (int[] values, int count)
    {
        int digits = 1, max_value = 9;

        for (int i = 0; i < count; ++i)
        {
            int x = values[i];

            if (m_buffer.Length - m_write_pos < SPACE_RESERVE)
                Flush();

            while (x > max_value)
                if (++digits < 10)
                    max_value = max_value * 10 + 9;
                else
                    max_value = int.MaxValue;               

            int n = x, p = m_write_pos + digits, e = p + 1;

            m_buffer[p] = (byte)'\n';

            while (n >= 10)
            {
                int q = n / 100, w = m_double_digit_lookup[n - q * 100];
                n = q;
                m_buffer[--p] = (byte)w;
                m_buffer[--p] = (byte)(w >> 8);
            }

            if (n != 0 || x == 0)
                m_buffer[--p] = (byte)((byte)'0' + n);

            m_write_pos = e;
        }
    }
}

Cela prend moins de 1 ms pour écrire 10000 nombres (triés). C'est une classe statique car elle est destinée à l'inclusion textuelle dans les soumissions de défi de codage, avec un minimum de tracas et un minimum de surcoût.

En général, j’ai trouvé que c’était beaucoup plus rapide si le travail était centré sur des lots entiers, c’est-à-dire tamiser une certaine plage, puis extraire tous les nombres premiers dans un vecteur / tableau, puis éliminer tout le tableau, puis tamiser la plage suivante, etc. au lieu de tout mélanger ensemble. Le fait de disposer de fonctions distinctes axées sur des tâches spécifiques facilite également la combinaison, la réutilisation et le développement / test.


Le code Mathcad suivant a calculé le premier million de nombres premiers en moins de 3 minutes.

Gardez à l'esprit que cela utiliserait des doubles en virgule flottante pour tous les nombres et serait interprété de manière fondamentale. J'espère que la syntaxe est claire.


Pas efficace du tout, mais vous pouvez utiliser une expression régulière pour tester les nombres premiers.

/^1?$|^(11+?)\1+$/

Ceci vérifie si, pour une chaîne composée de k 1 ” s, k n'est pas un nombre premier (c'est-à-dire si la chaîne est composée d'un “ 1 ” ou d'un nombre quelconque de “ 1 ” pouvant être exprimé sous la forme d'un produit n -ary).


Voici mon code VB 2008, qui trouve tous les nombres premiers <10 000 000 en 1 min 27 secondes sur mon ordinateur portable de travail. Il saute des nombres pairs et ne recherche que les nombres premiers qui sont <le carré du numéro de test. Il est uniquement conçu pour rechercher des nombres premiers compris entre 0 et une valeur sentinale.

Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles 
Button1.Click

    Dim TestNum As Integer
    Dim X As Integer
    Dim Z As Integer
    Dim TM As Single
    Dim TS As Single
    Dim TMS As Single
    Dim UnPrime As Boolean
    Dim Sentinal As Integer
    Button1.Text = "Thinking"
    Button1.Refresh()
    Sentinal = Val(SentinalTxt.Text)
    UnPrime = True
    Primes(0) = 2
    Primes(1) = 3
    Z = 1
    TM = TimeOfDay.Minute
    TS = TimeOfDay.Second
    TMS = TimeOfDay.Millisecond
    For TestNum = 5 To Sentinal Step 2
        Do While Primes(X) <> 0 And UnPrime And Primes(X) ^ 2 <= TestNum
            If Int(TestNum / Primes(X)) - (TestNum / Primes(X)) = 0 Then
                UnPrime = False
            End If
            X = X + 1

        Loop
        If UnPrime = True Then
            X = X + 1
            Z = Z + 1
            Primes(Z) = TestNum
        End If
        UnPrime = True
        X = 0
    Next
    Button1.Text = "Finished with " & Z
    TM = TimeOfDay.Minute - TM
    TS = TimeOfDay.Second - TS
    TMS = TimeOfDay.Millisecond - TMS
    ShowTime.Text = TM & ":" & TS & ":" & TMS
End Sub

Voici une solution C ++, utilisant une forme de SoE:

#include <iostream>
#include <deque>

typedef std::deque<int> mydeque;

void my_insert( mydeque & factors, int factor ) {
    int where = factor, count = factors.size();
    while( where < count && factors[where] ) where += factor;
    if( where >= count ) factors.resize( where + 1 );
    factors[ where ] = factor;
}

int main() {
    mydeque primes;
    mydeque factors;
    int a_prime = 3, a_square_prime = 9, maybe_prime = 3;
    int cnt = 2;
    factors.resize(3);
    std::cout << "2 3 ";

    while( cnt < 10000 ) {
        int factor = factors.front();
        maybe_prime += 2;
        if( factor ) {
            my_insert( factors, factor );
        } else if( maybe_prime < a_square_prime ) {
            std::cout << maybe_prime << " ";
            primes.push_back( maybe_prime );
            ++cnt;
        } else {
            my_insert( factors, a_prime );
            a_prime = primes.front();
            primes.pop_front();
            a_square_prime = a_prime * a_prime;
        }
        factors.pop_front();
    }

    std::cout << std::endl;
    return 0;
}

Notez que cette version du tamis peut calculer les nombres premiers indéfiniment.

A noter également, la STL deque prend du O(1) temps pour effectuer push_back , pop_front et l' accès aléatoire si subscripting.

L' resize opération prend du O(n) temps, où n est le nombre d'éléments ajoutés. En raison de la manière dont nous utilisons cette fonction, nous pouvons traiter ceci comme une petite constante.

Le corps de la while boucle dans my_insert est exécuté O(log log n) fois, où n égal à la variable maybe_prime . En effet, l'expression de condition de la while volonté est évaluée comme vraie une fois pour chaque facteur premier de maybe_prime . Voir " Fonction de diviseur " sur Wikipedia.

La multiplication par le nombre de fois my_insert appelé, montre qu'il faut du O(n log log n) temps pour lister les n premiers ... ce qui est, sans surprise, la complexité temporelle que le Sieve of Eratosthenes est supposé avoir.

Cependant, bien que ce code soit efficace, ce n'est pas le plus efficace ... Je suggérerais fortement d'utiliser une bibliothèque spécialisée pour la génération de nombres premiers, telle que primesieve . Toute solution réellement efficace et bien optimisée nécessitera plus de code que quiconque souhaite taper dans .


GateKiller , que diriez-vous d'ajouter une break à cela if dans la boucle foreach ? Cela accélèrerait beaucoup, car si 6 est divisible par 2, vous n'avez pas besoin de vérifier avec 3 et 5. (Je voterais de toute façon 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 + " ");
    }
}

Le tamis d'Eratosthène est la solution, en raison de sa simplicité et de sa rapidité. Ma mise en oeuvre en C

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>

int main(void)
{
    unsigned int lim, i, j;

    printf("Find primes upto: ");
    scanf("%d", &lim);
    lim += 1;
    bool *primes = calloc(lim, sizeof(bool));

    unsigned int sqrtlim = sqrt(lim);
    for (i = 2; i <= sqrtlim; i++)
        if (!primes[i])
            for (j = i * i; j < lim; j += i)
                primes[j] = true;

    printf("\nListing prime numbers between 2 and %d:\n\n", lim - 1);
    for (i = 2; i < lim; i++)
        if (!primes[i])
            printf("%d\n", i);

    return 0;
}

Temps de calcul du nombre de processeurs par le processeur (sur Pentium Dual Core E2140 1,6 GHz, Monocœur)

~ 4s pour lim = 100 000 000


using System;

namespace ConsoleApplication2
{
    class Program
    {
        static void Main(string[] args)
        {
            int n, i = 3, j, c;
            Console.WriteLine("Please enter your integer: ");
            n = Convert.ToInt32(Console.ReadLine());
            if (n >= 1)
            {
                Console.WriteLine("First " + n + " Prime Numbers are");
                Console.WriteLine("2");
            }
            for(j=2;j<=n;)
            {
                for(c=2;c<=i-1;c++)
                {
                    if(i%c==0)
                        break;
                }
                    if(c==i)
                    {
                        Console.WriteLine(i);
                        j++;
                    }
                    i++;                                
            }
            Console.Read();
        }
    }
}






primes