La façon la plus élégante de générer des nombres premiers

Question

Quelle est la manière la plus élégante d'implémenter cette fonction ?

ArrayList generatePrimes(int n)

Cette fonction génère le premier n primes (modifier : où n>1 ), donc generatePrimes(5) retournera un ArrayList con {2, 3, 5, 7, 11} . (Je fais ceci en C#, mais je suis heureux avec une implémentation Java - ou tout autre langage similaire (donc pas Haskell)).

Je sais comment écrire cette fonction, mais quand je l'ai fait hier soir, le résultat n'était pas aussi bon que je l'espérais. Voici ce que j'ai obtenu :

ArrayList generatePrimes(int toGenerate)
{
    ArrayList primes = new ArrayList();
    primes.Add(2);
    primes.Add(3);
    while (primes.Count < toGenerate)
    {
        int nextPrime = (int)(primes[primes.Count - 1]) + 2;
        while (true)
        {
            bool isPrime = true;
            foreach (int n in primes)
            {
                if (nextPrime % n == 0)
                {
                    isPrime = false;
                    break;
                }
            }
            if (isPrime)
            {
                break;
            }
            else
            {
                nextPrime += 2;
            }
        }
        primes.Add(nextPrime);
    }
    return primes;
}

Je ne suis pas trop préoccupé par la vitesse, même si je ne veux pas qu'il soit manifestement inefficace. Peu importe la méthode utilisée (naïve, tamis ou autre), mais je veux qu'elle soit assez courte et que son fonctionnement soit évident.

Editar : Merci à tous ceux qui ont répondu, même si beaucoup n'ont pas répondu à ma question. Pour réitérer, je voulais un morceau de code propre qui génère une liste de nombres premiers. Je sais déjà comment le faire de plusieurs façons différentes, mais j'ai tendance à écrire du code qui n'est pas aussi clair qu'il pourrait l'être. Dans ce fil de discussion, quelques bonnes options ont été proposées :

• Une version plus agréable de ce que j'avais à l'origine (Peter Smit, jmservera et Rekreativc)
• Une mise en œuvre très propre du tamis d'Eratosthène (starblue)
• Utilisez la fonction BigInteger et nextProbablePrime pour un code très simple, bien que je ne puisse pas imaginer qu'il soit particulièrement efficace (dfa)
• Utiliser LINQ pour générer paresseusement la liste des nombres premiers (Maghis)
• Mettre beaucoup de nombres premiers dans un fichier texte et les lire quand c'est nécessaire (darin)

Edit 2 : J'ai implémenté en C# deux des méthodes données ici, et une autre méthode non mentionnée ici. Elles trouvent toutes la première n efficacement (et j'ai un méthode décente de trouver la limite à fournir aux tamis).

Answer 1

Utilisez l'estimation

pi(n) = n / log(n)

pour le nombre de nombres premiers jusqu'à n pour trouver une limite, et ensuite utiliser un tamis. L'estimation sous-estime quelque peu le nombre de nombres premiers jusqu'à n, de sorte que le tamis sera légèrement plus grand que nécessaire, ce qui est correct.

C'est mon tamis Java standard, qui calcule le premier million de nombres premiers en une seconde environ sur un ordinateur portable normal :

public static BitSet computePrimes(int limit)
{
    final BitSet primes = new BitSet();
    primes.set(0, false);
    primes.set(1, false);
    primes.set(2, limit, true);
    for (int i = 0; i * i < limit; i++)
    {
        if (primes.get(i))
        {
            for (int j = i * i; j < limit; j += i)
            {
                primes.clear(j);
            }
        }
    }
    return primes;
}

Answer 2

Merci à tous ceux qui ont donné des réponses utiles. Voici mes implémentations de quelques méthodes différentes pour trouver le premier chiffre. n les nombres premiers en C#. Les deux premières méthodes sont à peu près ce qui a été posté ici. (J'ai l'intention de faire le tamis d'Atkin un jour, bien que je pense que ce ne sera pas aussi simple que les méthodes actuelles. Si quelqu'un voit un moyen d'améliorer l'une de ces méthodes, j'aimerais le savoir :-)

Méthode standard ( Peter Smit , jmservera , Rekreativc )

Le premier nombre premier est 2. Ajoutez-le à une liste de nombres premiers. Le prochain nombre premier est le prochain nombre qui n'est pas divisible de manière égale par un nombre de cette liste.

public static List<int> GeneratePrimesNaive(int n)
{
    List<int> primes = new List<int>();
    primes.Add(2);
    int nextPrime = 3;
    while (primes.Count < n)
    {
        int sqrt = (int)Math.Sqrt(nextPrime);
        bool isPrime = true;
        for (int i = 0; (int)primes[i] <= sqrt; i++)
        {
            if (nextPrime % primes[i] == 0)
            {
                isPrime = false;
                break;
            }
        }
        if (isPrime)
        {
            primes.Add(nextPrime);
        }
        nextPrime += 2;
    }
    return primes;
}

Cette méthode a été optimisée en ne testant la divisibilité que jusqu'à la racine carrée du nombre testé et en ne testant que les nombres impairs. On peut encore l'optimiser en ne testant que les nombres de la forme 6k+[1, 5] ou 30k+[1, 7, 11, 13, 17, 19, 23, 29] o ainsi de suite .

Le tamis d'Eratosthène ( starblue )

Cela trouve tous les nombres premiers à k . Pour faire une liste des premiers n les nombres premiers, nous devons d'abord déterminer la valeur approximative de la n e prime. La méthode suivante, comme décrit ici fait ça.

public static int ApproximateNthPrime(int nn)
{
    double n = (double)nn;
    double p;
    if (nn >= 7022)
    {
        p = n * Math.Log(n) + n * (Math.Log(Math.Log(n)) - 0.9385);
    }
    else if (nn >= 6)
    {
        p = n * Math.Log(n) + n * Math.Log(Math.Log(n));
    }
    else if (nn > 0)
    {
        p = new int[] { 2, 3, 5, 7, 11 }[nn - 1];
    }
    else
    {
        p = 0;
    }
    return (int)p;
}

// Find all primes up to and including the limit
public static BitArray SieveOfEratosthenes(int limit)
{
    BitArray bits = new BitArray(limit + 1, true);
    bits[0] = false;
    bits[1] = false;
    for (int i = 0; i * i <= limit; i++)
    {
        if (bits[i])
        {
            for (int j = i * i; j <= limit; j += i)
            {
                bits[j] = false;
            }
        }
    }
    return bits;
}

public static List<int> GeneratePrimesSieveOfEratosthenes(int n)
{
    int limit = ApproximateNthPrime(n);
    BitArray bits = SieveOfEratosthenes(limit);
    List<int> primes = new List<int>();
    for (int i = 0, found = 0; i < limit && found < n; i++)
    {
        if (bits[i])
        {
            primes.Add(i);
            found++;
        }
    }
    return primes;
}

Tamis de Sundaram

J'ai seulement découvert ce tamis récemment, mais elle peut être mise en œuvre assez simplement. Mon implémentation n'est pas aussi rapide que le tamis d'Eratosthène, mais elle est nettement plus rapide que la méthode naïve.

public static BitArray SieveOfSundaram(int limit)
{
    limit /= 2;
    BitArray bits = new BitArray(limit + 1, true);
    for (int i = 1; 3 * i + 1 < limit; i++)
    {
        for (int j = 1; i + j + 2 * i * j <= limit; j++)
        {
            bits[i + j + 2 * i * j] = false;
        }
    }
    return bits;
}

public static List<int> GeneratePrimesSieveOfSundaram(int n)
{
    int limit = ApproximateNthPrime(n);
    BitArray bits = SieveOfSundaram(limit);
    List<int> primes = new List<int>();
    primes.Add(2);
    for (int i = 1, found = 1; 2 * i + 1 <= limit && found < n; i++)
    {
        if (bits[i])
        {
            primes.Add(2 * i + 1);
            found++;
        }
    }
    return primes;
}

Answer 3

Je ressuscite une vieille question, mais je suis tombé dessus en jouant avec LINQ.

Ce code requiert .NET4.0 ou .NET3.5 avec les extensions parallèles.

public List<int> GeneratePrimes(int n) {
    var r = from i in Enumerable.Range(2, n - 1).AsParallel()
            where Enumerable.Range(1, (int)Math.Sqrt(i)).All(j => j == 1 || i % j != 0)
            select i;
    return r.ToList();
}

Answer 4

Vous êtes sur la bonne voie.

Quelques commentaires

• primes.Add(3) ; fait que cette fonction ne fonctionne pas pour nombre = 1

• Il n'est pas nécessaire de tester la division avec des nombres primaires plus grands que la racine carrée du nombre à tester.

Code suggéré :

ArrayList generatePrimes(int toGenerate)
{
    ArrayList primes = new ArrayList();

    if(toGenerate > 0) primes.Add(2);

    int curTest = 3;
    while (primes.Count < toGenerate)
    {

        int sqrt = (int) Math.sqrt(curTest);

        bool isPrime = true;
        for (int i = 0; i < primes.Count && primes.get(i) <= sqrt; ++i)
        {
            if (curTest % primes.get(i) == 0)
            {
                isPrime = false;
                break;
            }
        }

        if(isPrime) primes.Add(curTest);

        curTest +=2
    }
    return primes;
}

Answer 5

Vous devriez jeter un coup d'œil à primes probables . En particulier, jetez un coup d'œil à Algorithmes aléatoires y Test de primauté de Miller-Rabin .

Par souci d'exhaustivité, vous pourriez simplement utiliser java.math.BigInteger :

public class PrimeGenerator implements Iterator<BigInteger>, Iterable<BigInteger> {

    private BigInteger p = BigInteger.ONE;

    @Override
    public boolean hasNext() {
        return true;
    }

    @Override
    public BigInteger next() {
        p = p.nextProbablePrime();
        return p;
    }

    @Override
    public void remove() {
        throw new UnsupportedOperationException("Not supported.");
    }

    @Override
    public Iterator<BigInteger> iterator() {
        return this;
    }
}

@Test
public void printPrimes() {
    for (BigInteger p : new PrimeGenerator()) {
        System.out.println(p);
    }
}