Recursively find prime numbers

Introduction

As part of learning Python, I wrote code to recursively find prime numbers.

code

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]

in conclusion

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

Recursively find prime numbers
Prime numbers and divisors
Discrimination of prime numbers
Find prime numbers in Python as short as possible
Prime numbers in Python
This year's prime numbers
Determine prime numbers with python
Find the factorial prime factorization
Project Euler 10 "Sum of Prime Numbers"
It's a prime number ... Counting prime numbers ...
[Python] nCr mod Compute prime numbers
Algorithm learned with Python 4th: Prime numbers
I searched for prime numbers in python