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:

tex_37fee7ca12f920a4cf1e5eb87904b10d Finding Primes algorithms beginner brute force math python technical

This is useful to find out the number of divisors for a natural number. For example, 6 can be re-written as tex_c5c81484c12f2804ba05d63f11141a48 Finding Primes algorithms beginner brute force math python technical . Therefore the total number of divisors for 6 can be calculated as tex_f95ae1a060f6e604240cfbcab24c59da Finding Primes algorithms beginner brute force math python technical , which are 1, 2, 3, 6. In general, the number of divisors are equal to tex_5a71855e5cbce30e9700809a24f07168 Finding Primes algorithms beginner brute force math python technical

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 tex_68206d916dd6d84be5f480bd6e7e038f Finding Primes algorithms beginner brute force math python technical 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]

prime Finding Primes algorithms beginner brute force math python technical

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) —

GD Star Rating
loading...
733 words
Last Post: O(n) High-precision Division Between Two Integers
Next Post: Sleep Sorting in Python, using Threads

The Permanent URL is: Finding Primes

One Response

  1. sahbaz serdar

Leave a Reply