l'algorithme le plus rapide pour les tests de prime générale est AKS . L'article de Wikipedia le décrit en long et en lien avec le papier original.

si vous voulez trouver de grands nombres, regardez dans les nombres premiers qui ont des formes spéciales comme Mersenne nombres premiers .

l'algorithme que j'implémente habituellement (facile à comprendre et à coder) est le suivant (en Python):

def isprime(n):
    """Returns True if n is prime."""
    if n == 2:
        return True
    if n == 3:
        return True
    if n % 2 == 0:
        return False
    if n % 3 == 0:
        return False

    i = 5
    w = 2

    while i * i <= n:
        if n % i == 0:
            return False

        i += w
        w = 6 - w

    return True

c'est une variante de l'algorithme classique O(sqrt(N)) . Il utilise le fait qu'un premier (sauf 2 et 3) est de la forme 6k - 1 ou 6k + 1 et ne regarde que les diviseurs de cette forme.

parfois , si je veux vraiment de la vitesse et la portée est limitée , je mets en œuvre un pseudo-premier test basé sur Fermat'S little theorem . Si je veux vraiment plus de vitesse (c.-à-d. éviter o(sqrt (N)) algorithme tout à fait), je précalculer les faux positifs (voir Carmichael ) et faire une recherche binaire. C'est de loin le test le plus rapide que j'ai jamais mis en place, le seul inconvénient est que la portée est limitée.

La meilleure méthode, à mon avis, est d'utiliser ce qui est passé avant.

Il y a des listes de la première N nombres premiers sur internet avec N qui s'étend jusqu'à au moins cinquante millions de . Téléchargez les fichiers et utilisez-les, il est probable d'être beaucoup plus rapide que toute autre méthode que vous trouverez.

si vous voulez un algorithme réel pour faire vos propres nombres premiers, Wikipedia a toutes sortes de bonnes choses sur les nombres premiers ici , incluant des liens vers les différentes méthodes pour le faire , et" prime testing ici , à la fois des méthodes basées sur la probabilité et des méthodes déterministes rapides.

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

selon wikipedia, le tamis D'Eratosthène a complexité O(n * (log n) * (log log n)) et nécessite O(n) mémoire - donc c'est un assez bon endroit pour commencer si vous ne testez pas pour des nombres particulièrement grands.

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;
}
this is just c++ implementation of above  AKS algorithm

https://en.wikipedia.org/wiki/AKS_primality_test

En Python 3:

def is_prime(a):
if a < 2:
    return False
elif a!=2 and a % 2 == 0:
    return False
else:
    return all (a % i for i in range(3, int(a**0.5)+1) )

explication: Un nombre premier est un nombre divisible par lui-même et 1. Ex: 2,3,5 et 7...

1) si a<2: si " a " est inférieur à 2 ce n'est pas une prime.

2) elif a!= 2 et a % 2 = = 0: si "a" est divisible par 2 alors ce n'est certainement pas un prime. Mais si a=2 nous ne voulons pas évaluer cela comme c'est un nombre premier. D'où la condition d'un!= 2

3) retourner tous (a % i pour i dans la gamme (3, int(a 0.5)+1) ):** regardez D'abord ce que fait all() command en python. À partir de 3 Nous divisons "a" jusqu'à sa racine carrée (a**0.5). Si " a " est divisible, le résultat sera faux. Pourquoi racine carrée? Disons que a=16. La racine carrée de 16 = 4. On n'a pas besoin d'évaluer avant 15 ans. On a juste besoin de vérifier jusqu'à 4 h pour dire que ce n'est pas une prime.

Supplémentaire: Une boucle pour trouver tous les nombres premiers dans une gamme.

for i in range(1,100):
if is_prime(i):
    print("{} is a prime number".format(i) )

Python 3:

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

bien trop tard pour la fête, mais espérons que cela aide. Ceci est pertinent si vous cherchez de grands nombres premiers:

pour tester de grands nombres impairs, vous devez utiliser le test de Fermat et/ou le test de Miller-Rabin.

ces tests utilisent exponentiation modulaire qui est assez cher, pour n bits exponentiation dont vous avez besoin au moins n grande multiplication int et n grande division int. Ce qui signifie la complexité de l'exponentiation modulaire is O (n3).

donc avant d'utiliser les gros canons, vous devez faire pas mal de divisions d'essai. Mais ne le faites pas naïvement, il y a un moyen de les faire jeûner. D'abord multiplier autant de nombres premiers, ensemble, autant s'inscrit dans une les mots que vous utilisez pour les grands entiers. Si vous utilisez des mots de 32 bits, multipliez 3*5*7*11*13*17*19*23*29=3234846615 et calcule le plus grand diviseur commun avec le nombre que vous testez en utilisant L'algorithme euclidien. Après la première étape, le nombre est réduit en dessous de la taille de mot et continuer l'algorithme sans effectuer de remplir grande division entière. Si le GCD != 1, cela signifie qu'un des nombres premiers que vous avez multipliés ensemble divise le nombre, donc vous avez une preuve que ce n'est pas premier. Puis continuer 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 façon, vous pouvez faire 40 tours de test Miller-Rabin pour confirmer le nombre est premier, après 40 tours, vous pouvez être certain que le nombre est premier il n'y a que 2^-80 il est plus probable que votre matériel fonctionne mal...).

j'ai une fonction première qui fonctionne jusqu'à (2^61)-1 ici:

from math import sqrt
def isprime(num): num > 1 and return all(num % x for x in range(2, int(sqrt(num)+1)))

explication:

la fonction all() peut être redéfinie comme suit:

def all(variables):
    for element in variables:
        if not element: return False
    return True

la fonction all() passe simplement par une série de bools / nombres et renvoie False si elle voit 0 ou False .

la fonction sqrt() ne fait que racine carrée d'un nombre.

par exemple:

>>> from math import sqrt
>>> sqrt(9)
>>> 3
>>> sqrt(100)
>>> 10

la partie num % x renvoie le reste de num / X.

enfin, range(2, int(sqrt(num))) signifie qu'il va créer une liste qui commence à 2 et se termine à int(sqrt(num)+1)

pour plus d'informations sur la gamme, consultez ce site web !

la partie num > 1 ne fait que vérifier si la variable num est plus grande que 1, parce que 1 et 0 ne sont pas considérés des nombres premiers.

j'espère que cela a aidé :)

En Python:

def is_prime(n):
    return not any(n % p == 0 for p in range(2, int(math.sqrt(n)) + 1))

une conversion plus directe du formalisme mathématique en Python utiliserait tout(n % p != 0... ) , mais cela exige une évaluation stricte de toutes les valeurs de P. La version pas n'importe quelle version peut se terminer tôt si une valeur vraie est trouvée.

meilleur algorithme pour nombres premiers javascript

 function isPrime(num) {
      if (num <= 1) return false;
      else if (num <= 3) return true;
      else if (num % 2 == 0 || num % 3 == 0) return false;
      var i = 5;
      while (i * i <= num) {
        if (num % i == 0 || num % (i + 2) == 0) return false;
        i += 6;
      }
      return true
    }

idée similaire à l'algorithme AKS qui a été mentionnée""

public static boolean isPrime(int n) {

    if(n == 2 || n == 3) return true;
    if((n & 1 ) == 0 || n % 3 == 0) return false;
    int limit = (int)Math.sqrt(n) + 1;
    for(int i = 5, w = 2; i <= limit; i += w, w = 6 - w) {
        if(n % i == 0) return false;
        numChecks++;
    }
    return true;
}

pour déterminer si le ou les nombres dans une plage sont/sont premiers.

#!usr/bin/python3

def prime_check(*args):
    for arg in args:
        if arg > 1:     # prime numbers are greater than 1
            for i in range(2,arg):   # check for factors
                if(arg % i) == 0:
                    print(arg,"is not Prime")
                    print(i,"times",arg//i,"is",arg)
                    break
            else:
                print(arg,"is Prime")

            # if input number is less than
            # or equal to 1, it is not prime
        else:
            print(arg,"is not Prime")
    return

# Calling Now
prime_check(*list(range(101)))  # This will check all the numbers in range 0 to 100 
prime_check(#anynumber)         # Put any number while calling it will check.

myInp=int(input("Enter a number: "))
if myInp==1:
    print("The number {} is neither a prime not composite no".format(myInp))
elif myInp>1:
    for i in range(2,myInp//2+1):
        if myInp%i==0:
            print("The Number {} is not a prime no".format(myInp))
            print("Because",i,"times",myInp//i,"is",myInp)
            break
    else:
        print("The Number {} is a prime no".format(myInp))
else:
    print("Alas the no {} is a not a prime no".format(myInp))

on peut utiliser sympy .

import sympy

sympy.ntheory.primetest.isprime(33393939393929292929292911111111)

True

D'après sympy docs. La première étape consiste à rechercher des facteurs triviaux qui, s'ils sont trouvés, permettent un retour rapide. Ensuite, si le tamis est assez grand, l'utilisation non-bloquante de recherche sur le tamis. Pour de petits nombres, une série de tests déterministes de Miller-Rabin est effectuée avec des bases qui sont connues pour n'avoir aucun contre-échantillon dans leur gamme. Enfin, si le nombre est supérieur à 2 ^ 64, un test BPSW fort est effectuer. Bien qu'il s'agisse d'un premier test probable et nous croyons qu'il existe des contre-exemples, il n'existe pas de contre-exemples connus "151970920