Thursday, 19 January 2012
What is a prime number?
Any number which has only two divisors, number one and the number itself are said to be prime numbers. The numbers which are not prime are collectively termed as composite numbers.
- 2 is a prime number
- 4 is a composite number (divisible by 2)
- 7 is a prime number
Now, if we have to find a prime number we will generally check whether the number has any other divisors i.e. other than one and the number itself. This task is usually very time consuming for large digits.
Example: The number 123456789 would possibly require (123456789 – 2) instruction steps to be executed in order to find out its primality(property of a number being prime).
In computing it is very necessary to devise efficient algorithms to make decisions at a fast pace and at the same time consume lesser memory space. This can also be referred to time and space tradeoff for an algorithm. Time and space tradeoff: If we try to speed up a particular algorithm process, we may possibly require more memory and in an effort to decrease the memory space, we might obtain a slower processing speed.
Now we will discuss how to find a prime number.
We can find a prime number by checking for divisors from 2 to the n-1. If we don’t have any divisors, then the number is prime.
Now, if we deeply observe. Composite numbers have a property which says that a composite number can be factorized into two numbers one of which must be lesser than √n. Hence we only have to perform divisor checking operation from 2 to √n, thus improving efficiency.
Now to even obtain more speed up we can ignore all even numbers.
Now deeply if we observe again, we can perform the rule out operation for other numbers and hence rule out very large set of composite numbers. Thus it strikes to store a few prime numbers in memory and then test the input numbers for their primality. This of course would consume a few bytes extra but result in a faster way to process for primality. Time Space tradeoff afterall.
A few prime numbers might be obtained by the Sieve of Eratosthenes algorithm which finds all the prime numbers up to a limit we specify.
These were some of the naïve methods we could use for primality tests.
There are even some other tests which can be referred for more information such as:
- Fermat primality test
- Miller–Rabin primality test
- Solovay–Strassen primality test
- Pocklington primality test
Key Access knowledge:
- A primality test is used for cryptography besides some other fields of mathematics.
- 1 is not a prime number. Many mathematicians did consider it to be a prime number. In fact, many theorems and proofs hold true only if 1 is considered to be a prime number.
- In 2008 the record of largest prime number passed ten million digits, earning a $100,000 prize. The prizes are offered by the Electronic Frontier Foundation for record primes.
- There are around 100 types of prime numbers. Link
- The largest known prime number as of 2011 is approximately 13million digits long. Link