As part of learning Python, I wrote code to recursively find prime numbers.
This time, I used an Eratosthenes sieve.
The Eratosthenes Sieve (Sieve of Eratosthenes) is a simple algorithm for finding all prime numbers below a specified integer. It has this name because it is said to have been invented by the ancient Greek scientist Eratosthenes. (Wikipedia "[Eratosthenes 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) ”)
Below is the code.
Sieve.py
array = [i for i in range(2, 100)] #Range of values you want to find
prime = [2] #List of prime numbers
def Sieve(array, prime): #Eratosthenes Sieve
newArray = []
for i in array:
if i%prime[-1] != 0:
newArray.append(i)
prime.append(newArray[0]) #Add prime numbers to the list
if array[-1] == prime[-1]:
return prime #Returns a list of prime numbers
return Sieve(newArray, prime)
Prime = Sieve(array, prime)
print(Prime) #output
As a result, the prime numbers from 2 to ~~ 100 ~~ 99 were found (corrected on December 22, 2019).
output
[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]
It seems that there is an upper limit when dealing with recursion in Python. The upper limit and how to change it were explained in this article.
Thank you for visiting. If you have any suggestions, please leave them in the comments section.
Recommended Posts