Finding Primes

A prime number is a positive natural number that is greater than 1 and no other divisors other than 1 and itself. For example, 2, 3, 5 are primes but 4, 6, 8 are not. A positive nature number that is not prime is called a composite number.

Finding primes numbers are very common techniques required in number theory-based applications. For example, any positive nature number can be expressed using the multiplication product of the following format:

This is useful to find out the number of divisors for a natural number. For example, 6 can be re-written as . Therefore the total number of divisors for 6 can be calculated as , which are 1, 2, 3, 6. In general, the number of divisors are equal to

In computer science, finding primes can be efficiently constructed using the following two method: checking individual number and Sieve’s method.

To check if any given integer is prime is straightforward. Brute-force implementation is to list the numbers from 2 to itself minus one inclusive, and check if it can be divided by itself, it yes, then it is not a prime, otherwise it is a prime.

This can be improved by only checking a fewer numbers, for instance, only the numbers from 2 to are necessary. To further reduce the checking operations, only check 2, 3 and skip two numbers at a time, to next 5, 7, 9 … The reason for that is simple, if a number can not be divided by two, then it is an odd number, which surely cannot be divided by any even number that is greater than 2.

The following Python code will implement the first idea, which lists the prime numbers from 1 to 70.

#!/usr/bin/env python

maxn = 70

def isprime(n):
    if n <= 1:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    for i in xrange(3, int(n ** 0.5) + 1, 2):  # skip 1 number at a time
        if n % i == 0:
            return False
    return True

p = []
for i in xrange(1, maxn + 1):
    # check each number and add to the set if it is a prime
    if isprime(i):
        p.append(i)

# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67]
print p

The Python code n ** 0.5 is the same as sqrt(n),. but simpler, without the need to import the math package.

The second method is based on Sieve’s idea, and it is more efficient if you want to find a prime list rather than just want to know if a number is prime. The idea is to filter out the multiples of the primes in the list and the algorithm can be described as the following steps. [wiki link]

The following Python code illustrates this idea and gives the same prime number set from 1 to 70.

#!/usr/bin/env python

maxn = 70
u = [True] * (maxn + 1)
for i in xrange(2, maxn + 1):
    if u[i]:
        for j in xrange(i * i, maxn + 1, i):
            u[j] = False

#[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67]
print [x for x in xrange(2, maxn + 1) if u[x]]

–EOF (The Ultimate Computing & Technology Blog) —