performance - Code le plus efficace pour les 10000 premiers nombres premiers?

Translate

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.
This question and all comments follow the "Attribution Required."

Toutes les réponses

Translate

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

Si vous n'exécutez que les nombres 1 de plus et 1 de moins que les multiples de 6, cela pourrait être encore plus rapide, car tous les nombres premiers au-dessus de 3 sont à 1 d'un multiple de six.Ressource pour ma déclaration

La source
Translate

Je recommande un tamis, soit leTamis d'Ératosthèneou laTamis d'Atkin.

Le tamis ou Eratosthenes 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 que vous voulez, 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'à la fin de la liste. Tous les nombres qui ne sont pas barrés sont premiers.

De toute évidence, de nombreuses optimisations peuvent être effectuées pour accélérer le fonctionnement de cet algorithme, 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 comprendre tous les nombres premiers jusqu'à 1000000000 sur un ancien Pentium II-350

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

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

La source
Translate

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

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

La source
Translate

GateKiller, que diriez-vous d'ajouter unbreakpour queifdans leforeachboucle? Cela accélérerait les chosesbeaucoupcar si comme 6 est divisible par 2, vous n'avez pas besoin de vérifier avec 3 et 5. (je voterais quand même 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 + " ");
    }
}
La source
Translate

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

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

primes !! 10000est quasi instantané.

Références:


Le code ci-dessus est facilement modifié pour ne travailler que sur les cotes,primes = 2 : 3 : minus [5,7..] (foldr (\p r -> p*p : union [p*p+2*p, p*p+4*p..] r) [] (tail primes)). La complexité temporelle est beaucoup améliorée (à peu prèsJournalfacteur supérieur à l'optimum) en se repliant dans une structure arborescente, et la complexité de l'espace estconsidérablement amélioréparproduction d'amorces à plusieurs étages, dans

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 [email protected](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 signifié juste par juxtaposition,(:)est unles inconvénientsopérateur pour les listes, et(.)est un opérateur de composition fonctionnel:(f . g) x = (\y -> f (g y)) x = f (g x)).

La source
jfs
Translate

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

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

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

Compte tenu des complexités de calcul asymptotiques le longO(N)(pour Eratosthenes) etO(N/log(log(N)))(pour Atkin) on ne peut pas dire (pour petitN=10_000) quel algorithme, s'il est mis en œuvre, sera plus rapide.

Achim Flammenkamp a écrit dansLe 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'Eratosthène est surpassé par le tamis d'Atkins et de Bernstein qui utilise des formes quadratiques binaires irréductibles. Voir leur article pour des informations générales ainsi que le paragraphe 5 de la thèse de W. Galway. thèse.

Par conséquent pour10_000Le tamis d'Eratosthène peut être plus rapide que le tamis d'Atkin.

Pour répondre à OP, le code estprime_sieve.c(cité parnum1)

La source
Translate

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 1000000 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 choses. À moins que vous ne souhaitiez vraiment comprendre les algorithmes en écrivant le vôtre, il vous serait conseillé d'utiliser libGMP sous C.

La source
Translate

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

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

Ceci teste si, pour une chaîne composée dek1"S,kestpas prime(c'est-à-dire si la chaîne se compose d'un "1"Ou n'importe quel nombre de"1"S qui peuvent être exprimés enn-ary produit).

La source
Translate

J'ai adapté le code trouvé sur leCodeProjectpour créer ce qui suit:

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 cela sur mon serveur ASP.NET a pris environ 1 minute pour s'exécuter.

La source
Translate

Voici un tamis d'Eratosthène que j'ai écrit dans PowerShell il y a quelques jours. Il a un paramètre pour identifier le nombre de nombres premiers qui doivent être retournés.

#
# generate a list of primes up to a specific target using a sieve of eratosthenes
#
function getPrimes { #sieve of eratosthenes, http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
    param ($target,$count = 0)
    $sieveBound = [math]::ceiling(( $target - 1 ) / 2) #not storing evens so count is lower than $target
    $sieve = @($false) * $sieveBound
    $crossLimit = [math]::ceiling(( [math]::sqrt($target) - 1 ) / 2)
    for ($i = 1; $i -le $crossLimit; $i ++) {
        if ($sieve[$i] -eq $false) {
            $prime = 2 * $i + 1
            write-debug "Found: $prime"
            for ($x = 2 * $i * ( $i + 1 ); $x -lt $sieveBound; $x += 2 * $i + 1) {
                $sieve[$x] = $true
            }
        }
    }
    $primes = @(2)
    for ($i = 1; $i -le $sieveBound; $i ++) {
        if($count -gt 0 -and $primes.length -ge $count) {
            break;
        }
        if($sieve[$i] -eq $false) {
            $prime = 2 * $i + 1
            write-debug "Output: $prime"
            $primes += $prime
        }
    }
    return $primes
}
La source
Translate

Tamis d'Ératosthèneest la voie à suivre, en raison de sa simplicité et de sa rapidité. Mon implémentation 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 CPU pour trouver les nombres premiers (sur Pentium Dual Core E2140 1,6 GHz, en utilisant un seul cœur)

~ 4s pour lim = 100 000 000

La source
Translate

S'adapter et suivreGateKiller, voici la version finale que j'ai utilisée.

    public IEnumerable<long> PrimeNumbers(long number)
    {
        List<long> primes = new List<long>();
        for (int i = 2; primes.Count < number; i++)
        {
            bool divisible = false;

            foreach (int num in primes)
            {
                if (i % num == 0)
                    divisible = true;

                if (num > Math.Sqrt(i))
                    break;
            }

            if (divisible == false)
                primes.Add(i);
        }
        return primes;
    }

C'est fondamentalement la même chose, mais j'ai ajouté la suggestion "break on Sqrt" et j'ai changé certaines des variables pour qu'elles correspondent mieux à moi. (Je travaillais sur Euler et j'avais besoin du 10001ème prime)

La source
Translate

Le tamis semble être la mauvaise réponse. Le tamis vous donne les nombres premiersJusqu'àun numéroN, pas len premiernombres premiers. Exécutez @Imran ou @Andrew Szeto, et vous obtenez les nombres premiers jusqu'à N.

Le tamis peut encore être utilisable si vous continuez à essayer des tamis pour des nombres de plus en plus grands jusqu'à ce que vous atteigniez une certaine taille de votre jeu de résultats, et utilisez une certaine mise en cache des nombres déjà obtenus, mais je pense que ce ne serait toujours pas plus rapide qu'une solution comme @ Pat .

La source
Translate

En Python

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

lealgorithme deque sieve mentionné par BenGoldbergmérite un examen plus approfondi, non seulement parce qu'il est très élégant mais aussi parce qu'il peut parfois être utile en pratique (contrairement au tamis d'Atkin, qui est un exercice purement académique).

L'idée de base de l'algorithme deque sieve est d'utiliser un petit tamis glissant qui est juste assez grand pour contenir au moins un multiple séparé pour chacun des facteurs premiers actuellement `` 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 mobile. Une autre différence avec le SoE est que le tamis deque stocke les facteurs réels dans les emplacements des composites, et non des booléens.

L'algorithme étend la taille de la fenêtre de tamisage selon les besoins, ce qui se traduit par des performances assez uniformes sur une large plage jusqu'à ce que le tamis commence à dépasser sensiblement la capacité du cache L1 du processeur. Le dernier premier qui correspond parfaitement est 25 237 523 (le 1 579 791e premier), ce qui donne un chiffre approximatif pour la plage de fonctionnement raisonnable de l'algorithme.

L'algorithme est assez simple et robuste, et il a même des performances sur une plage beaucoup plus large qu'un tamis non segmenté d'Eratosthène. Ce dernier est beaucoup plus rapide tant que son tamis s'insère complètement dans le cache, c'est-à-dire jusqu'à 2 ^ 16 pour un tamis à cote seule avec des booléens de la taille d'un octet. Puis 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 sieve en C #, car je trouve ce langage - malgré ses nombreux défauts - 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 gratuitLINQPadce qui permet de plonger directement, sans tout le désordre avec la mise en place de projets, makefiles, répertoires ou autre, et cela me donne le même degré d'interactivité qu'une invite python).

C # n'a pas de type deque explicite mais le plainList<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 sortir sqrt (n) de n nombres premiers. À quoi cela servirait-il de supprimer 100 nombres premiers et de laisser 9900? Au moins de cette façon, tous les nombres premiers sont collecté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 manière la plus simple de comprendre l'algorithme est probablement de l'imaginer comme un tamis segmenté spécial d'Eratosthène avec une taille de segment de 1, accompagné d'une zone de débordement où les nombres premiers s'arrêtent lorsqu'ils tirent sur la fin du segment. Sauf que la seule cellule du segment (akasieve[0]) a déjà été tamisé lorsque nous y arrivons, car il a été écrasé alors qu'il faisait partie de la zone de débordement.

Le nombre représenté parsieve[0]est tenu danssieve_base, bien quesieve_frontouwindow_baseserait également un bon nom qui permet de faire des parallèles avec le code de Ben ou des implémentations de tamis segmentés / fenêtrés.

Sisieve[0]contient une valeur non nulle, alors cette valeur est un facteur desieve_base, qui peut ainsi être reconnu comme composite. Puisque la cellule 0 est un multiple de ce facteur, il est facile de calculer son prochain saut, 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'à ce que nous trouvions un multiple du facteur où aucun autre facteur n'est actuellement parqué (en étendant le tamis si nécessaire). Cela signifie également qu'il n'est pas nécessaire de stocker les décalages de travail courants des différents nombres premiers d'un segment à l'autre, comme dans un tamis segmenté normal. Chaque fois que nous trouvons un facteursieve[0], son décalage de travail actuel est 0.

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

Maintenant le cassieve[0] == 0 && sieve_base < current_prime_squareds'explique facilement: cela signifie quesieve_basene peut pas être un multiple de l'un des nombres premiers plus petit que le nombre premier courant, 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 au carré du premier courant. Il doit donc s'agir d'un nouveau premier.

L'algorithme est évidemment inspiré du Tamis d'Eratosthène, mais il est tout aussi évidemment très différent. Le tamis d'Eratosthène tire sa vitesse supérieure de la simplicité de ses opérations élémentaires: une seule addition d'index et un stockage pour chaque étape de l'opération est tout ce qu'il fait pendant de longues périodes de temps.

Voici un tamis d'ératosthène simple et non segmenté que j'utilise normalement pour tamiser les nombres premiers de facteurs dans la plage ushort, c'est-à-dire jusqu'à 2 ^ 16. Pour cet article, je l'ai modifié pour qu'il fonctionne au-delà de 2 ^ 16 en le remplaçantintpourushort

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 Kio-octets sera dépassé mais la fonction est toujours très rapide (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 qu'il ne peut pas amortir efficacement ses frais généraux car il effectue toujours le tronçon le plus court possible de croisements d'affilée. (exactement un seul barrage, après avoir sauté tous les multiples qui ont déjà été barrés).

Remarque: le code C # utiliseintau lieu deuintcar les nouveaux compilateurs ont l'habitude de générer du code de qualité inférieure pouruint, probablement pour pousser les gens vers des entiers signés ... Dans la version C ++ du code ci-dessus, j'ai utiliséunsignedpartout, naturellement; le benchmark devait être en C ++ car je voulais qu'il soit basé sur un type deque supposé adéquat (std::deque<unsigned>; il n'y a eu aucun gain de performance en utilisantunsigned short). Voici les chiffres de 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 à peu près exactement le double des timings C ++, ce qui est plutôt bon pour C # et cela montre queList<int>n'est pas en reste même s'il est abusé comme un deque.

Le code de tamis simple souffle toujours le deque 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 le débordement du cache associé). 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 tamis à 3 niveaux, et elle 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 pour extraire les nombres premiers tamisés (mod 3 échelonné et déroulé deux fois, ou mod 15 et déroulé une fois), et encore plus de performances pourraient être extraites de le code en utilisant une roue mod 16 ou mod 30 avec toutes les garnitures (c'est-à-dire déroulage complet pour tous les résidus). Quelque chose comme ça est expliqué dans ma réponse àTrouver un nombre premier positionné en premiersur la révision du code, où un problème similaire a été discuté. Mais il est difficile de voir l'intérêt d'améliorer les temps inférieurs à la milliseconde pour une tâche ponctuelle ...

Pour mettre les choses un peu en perspective, voici les timings C ++ pour 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 (aucun minutage C ++ disponible, car je ne fais des défis de code qu'en C # pour le moment).

Les choses peuvent sembler résolument différentes dans un langage interprété comme Python où chaque opération a un coût élevé et la surcharge de l'interpréteur éclipse toutes les différences dues à des branches prédites ou mal prédites ou à des opérations de sous-cycle (décalage, ajout) par rapport aux opérations multi-cycles (multiplication , et peut-être même division). Cela ne peut qu'éroder l'avantage de simplicité du tamis d'Eratosthène, et cela pourrait rendre la solution deque un peu plus attrayante.

De plus, bon nombre des horaires indiqués par d'autres répondants sur ce sujet sont probablement dominés partemps de sortie. C'est une guerre entièrement 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 aucune surcharge.

En général, j'ai trouvé que c'étaitbeaucoupplus rapide si un travail ciblé est effectué sur des lots entiers, ce qui signifie tamiser une certaine plage, puis extraire tous les nombres premiers dans un vecteur / tableau, puis faire exploser tout le tableau, puis tamiser la plage suivante et ainsi de suite, au lieu de tout mélanger. Le fait d'avoir des fonctions distinctes axées sur des tâches spécifiques facilite également le mélange et la correspondance, permet la réutilisation et facilite le développement / les tests.

La source
Translate

Voici mon code VB 2008, qui trouve tous les nombres premiers <10 000 000 en 1 min 27 s sur mon ordinateur portable de travail. Il saute les nombres pairs et ne recherche que les nombres premiers qui sont <le carré du nombre de test. Il est uniquement conçu pour trouver des nombres premiers de 0 à 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
La source
Translate

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 à virgule flottante pour tous les nombres et est essentiellement interprété. J'espère que la syntaxe est claire.

enter image description here

La source
Translate

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 Sieve peut calculer des nombres premiers indéfiniment.

A noter également, la STLdequeprendO(1)le temps de jouerpush_back, pop_front, et accès aléatoire par souscription.

leresizel'opération prendO(n)temps, oùnest le nombre d'éléments ajoutés. En raison de la façon dont nous utilisons cette fonction, nous pouvons traiter ceci est une petite constante.

Le corps duwhileboucle dansmy_insertest exécutéO(log log n)fois, oùnégale la variablemaybe_prime. C'est parce que l'expression de condition de lawhileévaluera à vrai une fois pour chaque facteur premier demaybe_prime. Voir "Fonction diviseur"sur Wikipédia.

Multiplier par le nombre de foismy_insertest appelé, montre qu'il fautO(n log log n)temps de listernnombres premiers ... ce qui est, sans surprise, la complexité temporelle que le Tamis d'Eratosthène est censé avoir.

Cependant, alors que ce codeisefficace, ce n'est pas lele plus efficace... Je suggérerais fortement d'utiliser une bibliothèque spécialisée pour la génération de nombres premiers, telle queprimesieve. Toute solution vraiment efficace et bien optimisée nécessitera plus de code que quiconque ne souhaite en saisir dans Stackoverflow.

La source
S_R
Translate

En utilisant Sieve of Eratosthenes, le calcul est bien plus rapide comparé à l'algorithme des nombres premiers "connus à l'échelle".

En utilisant le pseudocode de son wiki (https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes), Je peux avoir la solution sur 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.

La source
Translate

Je passe du temps à écrire un programme calculant beaucoup de nombres premiers et c'est le code que je suis utilisé pour calculer un fichier texte contenant les premiers 1.000.000.000 de nombres premiers. C'est en allemand, mais la partie intéressante est la méthodecalcPrimes(). Les nombres premiers sont stockés dans un tableau appelé Primzahlen. Je recommande un processeur 64 bits car les calculs sont 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);
        }
    }
}
La source
Translate

J'ai écrit ceci en utilisant python, car je viens de commencer à l'apprendre, et cela fonctionne parfaitement. Le 10 000ème prime généré par ce code comme indiquéhttp://primes.utm.edu/lists/small/10000.txt. Pour vérifier sinest premier ou pas, divisernpar les chiffres de2àsqrt(n). Si l'un de cette plage de nombres se divise parfaitementnalors ce n'est pas prime.

import math
print ("You want prime till which number??")
a = input()
a = int(a)
x = 0
x = int(x)
count = 1
print("2 is prime number")
for c in range(3,a+1):
    b = math.sqrt(c)
    b = int(b)
    x = 0
    for b in range(2,b+1):
        e  = c % b
        e = int(e)
        if (e == 0):
            x = x+1
    if (x == 0):
        print("%d is prime number" % c)
        count = count + 1
print("Total number of prime till %d is %d" % (a,count))
La source
Translate

Je travaille sur la recherche de nombres premiers depuis environ un an. C'est ce que j'ai trouvé le plus rapide:

import static java.lang.Math.sqrt;
import java.io.PrintWriter;
import java.io.File;
public class finder {
    public static void main(String[] args) {
        primelist primes = new primelist();
        primes.insert(3);
        primes.insert(5);
        File file = new File("C:/Users/Richard/Desktop/directory/file0024.txt");
        file.getParentFile().mkdirs();
        long time = System.nanoTime();
        try{
            PrintWriter printWriter = new PrintWriter ("file0024.txt"); 
            int linenum = 0;
            printWriter.print("2");
            printWriter.print (" , ");
            printWriter.print("3");
            printWriter.print (" , ");
            int up;
            int down;           
            for(int i =1; i<357913941;i++){//
                if(linenum%10000==0){
                    printWriter.println ("");
                    linenum++;
                }
                down = i*6-1;
                if(primes.check(down)){
                    primes.insert(down);
                    //System.out.println(i*6-1);
                    printWriter.print ( down );
                    printWriter.print (" , ");
                    linenum++;  
                }
                up = i*6+1;
                if(primes.check(up)){
                    primes.insert(up);
                    //System.out.println(i*6+1);
                    printWriter.print ( up );
                    printWriter.print (" , ");
                    linenum++;  
                }
            }
            printWriter.println ("Time to execute");
            printWriter.println (System.nanoTime()-time);
            //System.out.println(primes.length);
            printWriter.close ();
        }catch(Exception e){}
    } 
}
class node{
    node next;
    int x;
    public node (){
        node next;
        x = 3;
    }
    public node(int z) {
        node next;
        x = z;
    }
}
class primelist{
    node first;
    int length =0;
    node current;
    public void insert(int x){
        node y = new node(x);
        if(current == null){
            current = y;
            first = y;
        }else{
            current.next = y;
            current = y;
        }
        length++;
    }
    public boolean check(int x){
        int p = (int)sqrt(x);
        node y = first;
        for(int i = 0;i<length;i++){
            if(y.x>p){
                return true;
            }else if(x%y.x ==0){
                return false;
            }
            y = y.next;
        }
        return true;
    }
}

1902465190909 nanosecondes pour arriver à 2147483629 à partir de 2.

La source
Translate

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

  1. Tout d'abord, tout nombre non premier est un composé de multiples de nombres premiers donc ce code teste en divisant le nombre de test par des nombres premiers plus petits au lieu d'un nombre quelconque, cela diminue le calcul d'au moins 10 fois pour un nombre à 4 chiffres et même plus pour un plus grand nombre
  2. deuxièmement, en plus de diviser par des nombres premiers, il ne divise que par des nombres premiers qui sont plus petits ou égaux à la racine du nombre testé, réduisant encore davantage les calculs, cela fonctionne car tout nombre supérieur à la racine du nombre aura un nombre homologue 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 soucier d'un nombre supérieur à la racine du nombre testé.

Exemple de sortie pour les 10 000 premiers nombres premiers
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 êtes sur Windows ou Visual Studio, cela devrait être bien mais sous Linux, vous devez compiler le code en utilisant l'argument -lm ou le code peut 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);
}
La source
Translate

Voici le code que j'ai fait:


enter code here
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT*/   

unsigned long int n;

int prime(unsigned long int);

scanf("%ld",&n);

unsigned long int val;

for(unsigned long int i=0;i<n;i++)
{
    int flag=0;

    scanf("%ld",&val);

    flag=prime(val);

    if(flag==1)
        printf("yes\n");

    else
        printf("no\n");
}

return 0;

}

int prime(unsigned long int n)
{

if(n==2) return 1;

else if (n == 1||n%2==0)  return 0;

for (unsigned long int i=3; i<=sqrt(n); i+=2)
    if (n%i == 0)
        return 0;

return 1;
}
La source
Translate

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
La source
Translate

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 de 2 à 10.
  2. S'il s'agit d'un nombre impair, ne divisez que par un nombre impair, et vice versa. Comme pour 21, divisez par 3, 5, 7, 9 uniquement.

Méthode la plus efficace que je connaisse jusqu'à présent.

La source
Translate

Puisque vous voulez seulement 10000 premiers nombres premiers, plutôt que de coder un algorithme complexe, je suggérerai 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 l'appel est primordial car vous en avez besoin

for(int i=1 ; i<=1000 ; i++){
    if(isPrime(i)){
       //do something
    }
}
La source
Translate
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();
        }
    }
}
La source