pour calculer un million de nombres premiers

Un simple crible d'Eratosthène fonctionne comme les battants. Ce calcule la de 1 000 000 e premier en moins d'une seconde sur ma boîte:

class PrimeSieve
{
    public List<int> Primes;

    private BitArray Sieve;

    public PrimeSieve(int max)
    {
        Primes = new List<int> { 2, 3 }; //Must include at least 2, 3.
        Sieve = new BitArray(max + 1);
        foreach (var p in Primes)
            for (var i = p * p; i < Sieve.Length; i += p) Sieve[i] = true;
    }

    public int Extend()
    {
        var p = Primes.Last() + 2; //Skip the even numbers.
        while (Sieve[p]) p += 2;
        for (var i = p * p; i < Sieve.Length; i += p) Sieve[i] = true;
        Primes.Add(p);
        return p;
    }
}

EDIT: tamisage de façon optimale commence à partir de p^2, pas de 2p, comme Ness correctement points (composé de tous les numéros ci-dessous p^2 aura été marquée dans les précédentes itérations).

OriginalL'auteur Rafe

Clé de choses:

1. Sauter tous les nombres pairs. Commencez par 5, et juste ajouter deux à la fois.
2. 1 n'est pas un nombre premier...
3. Tester un certain nombre par trouver le mod de tous les nombres premiers jusqu'à la racine carrée du nombre. Pas besoin de tester n'importe quoi mais les nombres premiers.

OriginalL'auteur PearsonArtPhoto

Premier, 1 n'est pas un nombre premier.

Deuxième, la millionième premier est 15,485,863, de sorte que vous devez être prêt pour certaines grandes de traitement des données.

Troisième, vous voudrez probablement utiliser le Crible d'Eratosthène; voici une version simple:

function sieve(n)
    bits := makeArray(0..n, True)
    for p from 2 to n step 1
        if bits[p]
            output p
            for i from p*p to n step p
                bits[i] := False

Qui ne peuvent pas travailler pour la taille du tableau que vous aurez besoin de calculer le premier million de nombres premiers. Dans ce cas, vous aurez envie de mettre en œuvre une segmentation Crible d'Eratosthène.

J'ai fait beaucoup de travail avec nombres premiers à mon blog, y compris un essai qui fournit une optimisation du Crible d'Eratosthène, avec des implémentations dans les cinq langages de programmation.

Peu importe ce que vous faites, avec tout langage de programmation, vous devriez être en mesure de calculer le premier million de nombres premiers en pas plus de quelques secondes.

OriginalL'auteur user448810

Voici une solution javascript qui utilise la récursivité et itération pour atteindre le millionième premier. Ce n'est pas aussi rapide que le Tamis de Erathosthenes, mais ne nécessite pas de connaître la valeur de la millionième premier (c'est à dire, la taille de la nécessaire tamis) à l'avance:

function findPrimes(n, current, primes) {
    if (!n || current < 2) return []
    var isPrime = true
    for (var i = 0; i < primes.length; i++) {
        if (current % primes[i] == 0) {
            isPrime = false
            break
        }
    }
    if (isPrime) primes.push(current)
    if (primes.length < n) return findPrimes(n, current + 1, primes)
    else return primes
}

var primes = [2,3]
for (var i = 1; i <= 1000; i++) {
    primes = findPrimes(i*1000, primes[primes.length - 1]+1, primes)
    console.log(i*1000 + 'th prime: ' + primes[primes.length-1])
}
process.exit()

De sortie:

...
996000th prime: 15419293
997000th prime: 15435941
998000th prime: 15452873
999000th prime: 15469313
1000000th prime: 15485863

Process finished with exit code 0

OriginalL'auteur user2809286

N'est pas tout, après 5 se terminant par cinq divisible par 5, de sorte que vous pouvez ignorer les choses qui de droit(1,numb)<>"5" par exemple 987,985. J'en ai fait une dans Excel qui permettra de tester un million de chiffres pour les nombres premiers et de cracher dans une colonne en environ 15 secondes, mais il devient fou autour de 15 millions de

OriginalL'auteur jstiene