0%

Print Prime Numbers

Posted on Edited on In
Sieve of Eratosthenes

  1. Create a list contains number from 2 to n.

  2. Initially, set p to 2 which is the first prime number.

  3. Starting from p^2, mark p*(p+1), p*(p+2), p*(p+3)… as not prime numbers

  4. Find the smallest number greater than p that is not marked in the list, and repeat from step 3. If there is no such number, stop.

    Time Complexity: O(nlog(log(n)))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def SieveOfEratosthenes(n):
    # Create a boolean array "prime[0..n]" and initialize 
    # all entries it as true. A value in prime[i] will 
    # finally be false if i is Not a prime, else true. 
    prime = [True for i in range(n + 1)]
    p = 2
    while (p * p <= n):

        # If prime[p] is not changed, then it is a prime 
        if (prime[p] == True):

            # Update all multiples of p 
            for i in range(p * p, n + 1, p):
                prime[i] = False
        p += 1

Thanks to Krishan Kumar for providing above explanation. Extended version: Sieve of Eratosthenes in 0(n) time complexity.

Sieve of Sundaram
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
1) In general Sieve of Sundaram, produces primes smaller than 
   (2*x + 2) for a number given number x. Since we want primes 
   smaller than n, we reduce n-2 to half. We call it nNew.
       nNew = (n-2)/2;
   For example, if n = 102, then nNew = 50.

2) Create an array marked[n] that is going 
   to be used to separate numbers of the form i+j+2ij from 
   others where  1 <= i <= j

3) Initialize all entries of marked[] as false.

4) // Mark all numbers of the form i + j + 2ij as true
   // where 1 <= i <= j
   Loop for i=1 to nNew
        a) j = i; 
        b) Loop While (i + j + 2*i*j)  2, then print 2 as first prime.

6) Remaining primes are of the form 2i + 1 where i is
   index of NOT marked numbers. So print 2i + 1 for all i
   such that marked[i] is false.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
def SieveOfSundaram(n):
    # In general Sieve of Sundaram,
    # produces primes smaller
    # than (2*x + 2) for a number
    # given number x. Since we want
    # primes smaller than n, we
    # reduce n to half
    nNew = int((n - 2) / 2);

    # This array is used to separate
    # numbers of the form i+j+2ij
    # from others where 1 <= i <= j
    # Initialize all elements as not marked
    marked = [0] * (nNew + 1);

    # Main logic of Sundaram. Mark all
    # numbers of the form i + j + 2ij
    # as true where 1 <= i <= j
    for i in range(1, nNew + 1):
        j = i;
        while ((i + j + 2 * i * j) <= nNew):
            marked[i + j + 2 * i * j] = 1;
            j += 1;

            # Since 2 is a prime number
    if (n > 2):
        print(2, end=" ");

        # Print other primes. Remaining
    # primes are of the form 2*i + 1
    # such that marked[i] is false.
    for i in range(1, nNew + 1):
        if (marked[i] == 0):
            print((2 * i + 1), end=" ");