Comment créer la cartographie la plus compacte n → isprime(n) jusqu'à une limite N ?

Question

Naturellement, pour les bool isprime(number) il y aurait une structure de données que je pourrais interroger.
I définir le meilleur algorithme est l'algorithme qui produit une structure de données ayant la plus faible consommation de mémoire pour l'intervalle (1, N), où N est une constante.
Voici un exemple de ce que je recherche : Je pourrais représenter tous les nombres impairs par un bit, par exemple pour la plage de nombres donnée (1, 10), commence à 3 : 1110

Le dictionnaire suivant peut être davantage compressé, n'est-ce pas ? Je pourrais éliminer les multiples de cinq avec un peu de travail, mais les nombres qui se terminent par 1, 3, 7 ou 9 doivent être présents dans le tableau de bits.

Comment résoudre le problème ?

Answer 1

bool isPrime(int n)
{
    // Corner cases
    if (n <= 1)  return false;
    if (n <= 3)  return true;

    // This is checked so that we can skip 
    // middle five numbers in below loop
    if (n%2 == 0 || n%3 == 0) return false;

    for (int i=5; i*i<=n; i=i+6)
        if (n%i == 0 || n%(i+2) == 0)
           return false;

    return true;
}

Il s'agit de l'implémentation en c++ de ce qui précède

Answer 2

La meilleure méthode, à mon avis, consiste à utiliser ce qui a été fait auparavant.

Il existe des listes des premiers N sur l'internet avec N s'étendant au moins jusqu'à cinquante millions . Téléchargez les fichiers et utilisez-les, ce sera probablement beaucoup plus rapide que n'importe quelle autre méthode que vous trouverez.

Si vous voulez un algorithme réel pour créer vos propres nombres premiers, Wikipedia contient toutes sortes de bonnes informations sur les nombres premiers. aquí y compris des liens vers les différentes méthodes pour le faire, et des tests de premier ordre aquí Les méthodes d'évaluation de la qualité de l'eau, qu'elles soient basées sur les probabilités ou qu'elles soient déterministes et rapides.

Il devrait y avoir un effort concerté pour trouver le premier milliard (ou même plus) de nombres premiers et les publier sur le net quelque part afin que les gens puissent arrêter de faire ce même travail encore et encore et encore et ... :-)

Answer 3

Pour les grands nombres, vous ne pouvez pas simplement vérifier naïvement si le nombre candidat N n'est divisible par aucun des nombres inférieurs à sqrt(N). Il existe des tests beaucoup plus évolutifs, tels que la méthode Test de primalité de Miller-Rabin . Vous trouverez ci-dessous la mise en œuvre en python :

def is_prime(x):
    """Fast implementation fo Miller-Rabin primality test, guaranteed to be correct."""
    import math
    def get_sd(x):
        """Returns (s: int, d: int) for which x = d*2^s """
        if not x: return 0, 0
        s = 0
        while 1:
            if x % 2 == 0:
                x /= 2
                s += 1
            else:
                return s, x
    if x <= 2:
        return x == 2
    # x - 1 = d*2^s
    s, d = get_sd(x - 1)
    if not s:
        return False  # divisible by 2!
    log2x = int(math.log(x) / math.log(2)) + 1
    # As long as Riemann hypothesis holds true, it is impossible
    # that all the numbers below this threshold are strong liars.
    # Hence the number is guaranteed to be a prime if no contradiction is found.
    threshold = min(x, 2*log2x*log2x+1)
    for a in range(2, threshold):
        # From Fermat's little theorem if x is a prime then a^(x-1) % x == 1
        # Hence the below must hold true if x is indeed a prime:
        if pow(a, d, x) != 1:
            for r in range(0, s):
                if -pow(a, d*2**r, x) % x == 1:
                    break
            else:
                # Contradicts Fermat's little theorem, hence not a prime.
                return False
    # No contradiction found, hence x must be a prime.
    return True

Vous pouvez l'utiliser pour trouver d'énormes nombres premiers :

x = 10000000000000000000000000000000000000000000000000000000000000000000000000000
for e in range(1000):
    if is_prime(x + e):
        print('%d is a prime!' % (x + e))
        break

# 10000000000000000000000000000000000000000000000000000000000000000000000000133 is a prime!

Si vous testez des nombres entiers aléatoires, vous voudrez probablement tester d'abord si le nombre candidat est divisible par l'un des nombres premiers plus petits que, par exemple, 1000, avant d'appeler Miller-Rabin. Cela vous aidera à filtrer les nombres non premiers évidents tels que 10444344345.

Answer 4

Python 3 :

def is_prime(a):
    return a > 1 and all(a % i for i in range(2, int(a**0.5) + 1))

Answer 5

J'arrive bien trop tard, mais j'espère que cela vous aidera. Ceci est pertinent si vous recherchez de grands objectifs :

Pour tester les grands nombres impairs, il faut utiliser le test de Fermat et/ou le test de Miller-Rabin.

Ces tests utilisent l'exponentiation modulaire, ce qui est assez coûteux. n bits d'exponentiation, vous avez besoin d'au moins n la multiplication des grands nombres entiers et n grande division int. Ce qui signifie que la complexité de l'exponentiation modulaire est O(n³).

Avant d'utiliser les grands moyens, il faut donc procéder à un certain nombre de divisions d'essai. Mais ne le faites pas naïvement, il existe un moyen de les réaliser rapidement. Tout d'abord, multipliez autant de nombres premiers que possible dans les mots que vous utilisez pour les grands nombres entiers. Si vous utilisez des mots de 32 bits, multipliez 3*5*7*11*13*17*19*23*29=3234846615 et calculez le plus grand diviseur commun avec le nombre que vous testez en utilisant l'algorithme d'Euclide. Après la première étape, le nombre est réduit en dessous de la taille du mot et l'algorithme est poursuivi sans effectuer de divisions complètes de grands nombres entiers. Si le PGCD != 1, cela signifie que l'un des nombres premiers que vous avez multipliés ensemble divise le nombre, ce qui prouve qu'il n'est pas premier. Continuez avec 31*37*41*43*47 = 95041567, et ainsi de suite.

Une fois que vous avez testé plusieurs centaines (ou milliers) de nombres premiers de cette manière, vous pouvez faire 40 séries de tests de Miller-Rabin pour confirmer que le nombre est premier. Après 40 séries, vous pouvez être certain que le nombre est premier - il n'y a que 2^-80 chances qu'il ne le soit pas (il est plus probable que votre matériel fonctionne mal...).