Trouver des nombres premiers récursivement

introduction

Dans le cadre de l'apprentissage de Python, j'ai écrit du code pour trouver récursivement des nombres premiers.

code

Cette fois, j'ai utilisé un tamis Eratostenes.

Le tamis d'Eratosthène est un algorithme simple pour trouver tous les nombres premiers en dessous d'un entier spécifié. Il porte ce nom parce qu'il aurait été inventé par l'ancien scientifique grec Elatostines. (Wikipédia "[Eratostenes Sieve](https://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%A9%E3%83%88%E3%82%B9%E3%83%" 86% E3% 83% 8D% E3% 82% B9% E3% 81% AE% E7% AF% A9)

Ci-dessous le code.

Sieve.py


array = [i for i in range(2, 100)]  #Plage de valeurs que vous souhaitez rechercher
prime = [2]                  #Liste des nombres premiers

def Sieve(array, prime):     #Tamis Eratostenes
  newArray = []
  for i in array:
    if i%prime[-1] != 0:
      newArray.append(i)
  prime.append(newArray[0])  #Ajouter un nombre premier à la liste
  if array[-1] == prime[-1]:
    return prime             #Renvoie une liste de nombres premiers
  return Sieve(newArray, prime)

Prime = Sieve(array, prime)
print(Prime) #production

En conséquence, les nombres premiers de 2 à ~~ 100 ~~ 99 ont été trouvés (corrigé le 22 décembre 2019).

production


[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

en conclusion

Il semble qu'il existe une limite supérieure pour traiter la récurrence en Python. La limite supérieure et la manière de la modifier ont été expliquées dans cet article.

Merci pour votre visite. Si vous avez des suggestions, veuillez les laisser dans la section commentaires.

Recommended Posts

Trouver des nombres premiers récursivement
Nombres premiers et fractions
Discrimination des nombres premiers
Trouvez des nombres premiers avec un code aussi court que possible en Python
Nombre premier en Python
Le nombre premier de cette année
Juger les nombres premiers avec python
Trouvez la factorisation première de la puissance
Projet Euler 10 "Somme des nombres premiers"
C'est un nombre premier ... Comptez les nombres premiers ...
[Python] nCr mod Calculer les nombres premiers
J'ai cherché un nombre premier avec python