I use it myself occasionally, so I will post it on Qiita (´ ・ ω ・ `)
primes (x) is a method that stores prime numbers less than x in the list. The standard "Eratosthenes sieve" is used as the algorithm. I think the point that does not use filter etc. can be said to be a device.
Next, ʻis_prime (x)is a method that determines whether the integerx` is a prime number. The algorithm is still the standard "trial split". However, we are trying to improve efficiency by using pseudo-prime numbers (numbers that are not divisible by 2, 3, or 5).
import math
#Returns a list of prime numbers greater than or equal to 0 and integers x "less than"
def primes(x):
if x < 2: return []
primes = [i for i in range(x)]
primes[1] = 0 #1 is not a prime number
#Eratosthenes Sieve
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]
#Determine if the integer x is a prime number
def is_prime(x):
if x < 2: return False #There are no prime numbers less than 2
if x == 2 or x == 3 or x == 5: return True # 2,3,5 is a prime number
if x % 2 == 0 or x % 3 == 0 or x % 5 == 0: return False # 2,3,Multiples of 5 are composite numbers
#Trial split:Pseudo-prime number(A number that is not divisible by 2, 3, or 5)Divide one after another
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