Teaching Kids Programming – Generate Prime Numbers using Sieve of Eratosthenes Algorithms

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a number n, return a list of all prime numbers smaller than or equal to n in ascending order.

Constraints
n ≤ 100,000
Example 1
Input
n = 3
Output
[2, 3]
Example 2
Input
n = 10
Output
[2, 3, 5, 7]
Example 3
Input
n = 20
Output
[2, 3, 5, 7, 11, 13, 17, 19]

Generate Prime Numbers using Bruteforce Algorithm

We already know the optimised bruteforce approach to check if a number (positive) is a prime number by checking possible factors up to square root of N (instead of up to N). Therefore, we can iterate all positive numbers between 1 to N to see if the number is prime number. The overall time complexity is .

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def generatePrimeNumbers(self, n):
        ans = []
        def isPrime(n):
            if n <= 1:
                return False
            if n == 2:
                return True
            if n % 2 == 0:
                return False
            i = 3
            while i**2 <= n:
                if n % i == 0:
                    return False
                i += 2
            return True
        for i in range(2, n + 1):
            if isPrime(i):
                ans.append(i)
        return ans

class Solution:
    def generatePrimeNumbers(self, n):
        ans = []
        def isPrime(n):
            if n <= 1:
                return False
            if n == 2:
                return True
            if n % 2 == 0:
                return False
            i = 3
            while i**2 <= n:
                if n % i == 0:
                    return False
                i += 2
            return True
        for i in range(2, n + 1):
            if isPrime(i):
                ans.append(i)
        return ans

If we are not considering the output array, the space complexity is O(1) constant.

Sieve of Eratosthenes Algorithm of Generate Prime Numbers

We can do better by using Sieve of Eratosthenes Algorithm where we erase non-prime numbers from the list. Every iteration, we erase the multiples of the prime numbers from the list, the remaining ones are prime numbers.

1
2
3
4
5
6
7
8
9
10
11
12

class Solution:
    def generatePrimeNumbers(self, n):
        isPrimes = [False] * 2 + [True] * (n - 1)
        i = 2
        while i * i <= n:
            if isPrimes[i]:
                j = i + i
                while j <= n:
                    isPrimes[j] = False
                    j += i
            i += 1
        return [x for x in range(1, n + 1) if isPrimes[x]]

class Solution:
    def generatePrimeNumbers(self, n):
        isPrimes = [False] * 2 + [True] * (n - 1)
        i = 2
        while i * i <= n:
            if isPrimes[i]:
                j = i + i
                while j <= n:
                    isPrimes[j] = False
                    j += i
            i += 1
        return [x for x in range(1, n + 1) if isPrimes[x]]

The time complexity is O(N) and the space complexity is O(N) where we need to store the flags of each number (isPrime or not).

–EOF (The Ultimate Computing & Technology Blog) —