Check Prime

Tags: [math], [prime]

Link: https://zh.wikipedia.org/wiki/埃拉托斯特尼筛法 and https://en.wikipedia.org/wiki/Sieve\_of\_Eratosthenes

Given an integer n, find all primes which is less than or equal to n.

Solution: Sieve of Eratosthenes

import math

def find_primes(n):
    if n <= 1:
        return []

    nums = [True for _ in xrange(n + 1)]
    nums[0] = False
    nums[1] = False

    for num in xrange(2, int(math.ceil(math.sqrt(n)))):
        if not nums[num]:
            continue

        k = 0
        while num ** 2 + k * num <= n:
            nums[num ** 2 + k * num] = False
            k += 1

    primes = [num for num in xrange(2, n + 1) if nums[num]]
    return primes

if __name__ == '__main__':
    print 'Program is working'

    n = 120
    primes = find_primes(n)

    print 'There are {} primes in the range[2, {}]'.format(len(primes), n)
    for prime in primes:
        print prime

    print 'Program is end'

Revelation:

• The above algorithm is called "Sieve of Eratosthenes", reference: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

• The main idea of this algorithm is that create an one dimensional array, which contains n slots. Iterate all numbers in the range [2, ceil(sqrt(n))], for each num we multiple it to find all composite numbers based on the current num, and mark all these composite numbers in that one dimensional array. Finally the numbers in that one dimensional array have not been marked are the primes in the range [2, n].

• We can also use this algorithm to test whether n is prime or not. After we marking all composite numbers in the array (which we named it as nums here), we just need check nums[n] is True or False, nums[n] = True means n is prime, otherwise n is a composite number.

Note:

• Time complexity = O(nlg(lgn)), n is the given input.

Explanation of "num ** 2 + k * num", k= 0, 1, 2, 3, ...

• For example, given n, so we want to find all primes in the range[2, n].
• We iterate the numbers from 2 to ceil(sqrt(n)), the first num is 2. Based on the algorithm, we want to mark all 2 multiple numbers as composite numbers. These numbers are 4, 6, 8, 10, ... It seems that if i = 2, then the 2 multiple numbers should be i * (i + 0), i * (i + 1), i * (i + 2), i * (i + 3),...i * (i + k), the limitation is i * (i * k) <= n.
• i * (i + k) = i^2 + i * k, k = 0, 1, 2, 3, 4, .. ; limitation: i^2 + i * k <= n.

Explanation of "for num in xrange(2, int(math.ceil(math.sqrt(n)))):"

• Question: Why the limitation of max times of the iterations are math.ceil(math.sqrt(n))?
• Look at our inner loop, "while num ** 2 + k * num <= n:", combining with explanation of "i^2 + i * k", here num is i. We know if i is greater than sqrt(n), i^2 must be greater than n, which means if i > sqrt(n), the inner loop will not happen. So on our outer loop, we can just set the max iteration times is sqrt(n).

There is another way to implement the above algorithm, based on the explanation of "i^2 + k * i", k = 0, 1, 2, 3,...

import math

def find_primes(n):
    if n <= 1:
        return []

    nums = [True for _ in xrange(n + 1)]
    for num in xrange(2, int(math.ceil(math.sqrt(n)))):
        if not nums[num]:
            continue
        for multiple in xrange(2, n + 1):
            if num * multiple < len(nums):
                nums[num * multiple] = False
            else:
                break

    primes = []
    for num in xrange(2, n + 1):
        if nums[num]:
            primes.append(num)

    return primes

if __name__ == '__main__':
    print 'Program is working'

    n = 120
    primes = find_primes(n)

    print 'There are {} primes in the range[2, {}]'.format(len(primes), n)
    for prime in primes:
        print prime

    print 'Program is end'