Je l'utilise moi-même de temps en temps, donc je le posterai sur Qiita (´ ・ ω ・ `)
«primes (x)» est une méthode pour stocker les nombres premiers inférieurs à «x» dans la liste. Le "tamis Eratostenes" standard est utilisé comme algorithme. Je pense que le point qui n'utilise pas «filter», etc. peut être considéré comme un appareil.
Ensuite, ʻis_prime (x) est une méthode pour déterminer si l'entier x` est un nombre premier. L'algorithme est toujours la "division d'essai" standard. Cependant, nous essayons d'améliorer l'efficacité en utilisant des nombres pseudo-premiers (nombres qui ne sont pas divisibles par 2, 3 ou 5).
import math
#Renvoie une liste de nombres premiers supérieurs ou égaux à 0 et d'entiers x "inférieurs à"
def primes(x):
if x < 2: return []
primes = [i for i in range(x)]
primes[1] = 0 #1 n'est pas un nombre premier
#Tamis Eratostenes
for prime in primes:
if prime > math.sqrt(x): break
if prime == 0: continue
for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0
return [prime for prime in primes if prime != 0]
#Détermine si l'entier x est un nombre premier
def is_prime(x):
if x < 2: return False #Il n'y a pas de nombres premiers inférieurs à 2
if x == 2 or x == 3 or x == 5: return True # 2,3,5 est un nombre premier
if x % 2 == 0 or x % 3 == 0 or x % 5 == 0: return False # 2,3,Les multiples de 5 sont des nombres composites
#Scission d'essai:Pseudo nombre premier(Nombres non divisibles par 2, 3 ou 5)Se diviser les uns après les autres
prime = 7
step = 4
while prime <= math.sqrt(x):
if x % prime == 0: return False
prime += step
step = 6 - step
return True
if __name__ == '__main__':
print(primes(30)) #=> [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
ls = [x for x in range(30) if is_prime(x)]
print(ls) #=> [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Recommended Posts