Ad
simon-tigervs.ozichukwu

Get all primes up to a given number

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)]
simon-tiger

Get all primes up to a given number

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