from math import sqrt def is_prime(num): for newnum in range(2, int(sqrt(num)) + 1): if num % newnum == 0: return False return True def get_primes(num): return [n for n in range(2, num + 1) if is_prime(n)]
- from math import sqrt
- def is_prime(num):
- for newnum in range(2, int(sqrt(num)) + 1):
- if num % newnum == 0:
- return False
return False if num == 1 else True- return True
- def get_primes(num):
return [n for n in range(1, num + 1) if is_prime(n)]- return [n for n in range(2, num + 1) if is_prime(n)]
Get all prime numbers less than or equal to the input n
.
Examples
get_primes(10) # Output: [2, 3, 5, 7]
get_primes(50) # Output: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
get_primes(100) # 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]
get_primes(10000) # Output: [1229 elements]
Algorithm Description
This is the algorithm I used originally, but, feel free to fork this kumite and use your own algorthm!
1) Start with a list of all the numbers from 2 to n.
2) Mark all of the numbers divisible by 2.
3) Choose the smallest number untouched so far.
4) Mark all of the numbers divisible by the chosen number.
5) Repeat 3) and 4) until you've touched everything.
6) The chosen numbers are all the primes up to n.
def get_primes(n):
nums = list(range(2, n+1))
primes = []
while len(nums) > 0:
prime = nums[0]
del nums[0]
primes.append(prime)
for i in range(len(nums)-1, -1, -1):
if nums[i] % prime == 0:
del nums[i]
return primes
test.assert_equals(get_primes(10), [2, 3, 5, 7])
test.assert_equals(get_primes(50), [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47])
test.assert_equals(get_primes(100), [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])
test.assert_equals(len(get_primes(10000)), 1229)