Ad
Variables
Basic Language Features
Fundamentals
Conditional Statements
Control Flow
Loops
Arrays
Data Types
Code
Diff
  • 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)]
Variables
Basic Language Features
Fundamentals
Conditional Statements
Control Flow
Loops
Arrays
Data Types

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