A prime number (or a prime) is a natural number which has exactly two distinct natural number divisors: 1 and itself. The first twenty-six prime numbers are:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101.
Today the largest known prime number, found only in August 2008, is a 12 million digit number (a very large number) that took thousands of people and many distributed computers to determine and test. The discovery was hailed by Time magazine as the 29th top invention of 2008. There is a foundation called Electronic Frontier Foundation,
www.eff.org/awards/coop, that offers awards for finding very large prime numbers. The "next" award is $USD150K for the first person or group to find a prime number with at least 100,000,000 decimal digits.
Finding prime numbers has been "studied" for such a long time dating back to 300BC with the early Mathematicians from Ancient Greece. In fact the oldest recorded thoughts on prime numbers dates back 20,000 years ago to a "Ishango bone" found in the Nile river of Congo.
Today, there is still no known formula for finding prime numbers. However, people have developed methods or algorithms to determine if a given number is prime or to list a series of prime numbers.
The "quick way" to determine if a number is prime is based on the fact that since prime numbers are those with only 1 and itself as factors, we know that we are dealing with multiplication / division. So we can conclude that when testing a number we only need to test those numbers up to the square root of the number being tested. For eg. the number 49's square root is 7, therefore to test 49 you will only need to try up to the number 7 (7x7) - which of course is not prime. If you try the number 19, you would try 2, 3, 4 and stop because 5x5 is 25 which is greater than 19. Thus 19 is Prime.
If you want to build a list of prime numbers less than or equal to a given integer there is a method called Erotosthenes
en.wikipedia.org/wiki/Sieve_of_Eratosthenes which has 6 steps:
- Create a list of consecutive integers from two to your number, say n,: (2, 3, 4, ..., n).
- Initially, let p equal 2, the first prime number.
- Strike from the list all multiples of p greater than p eg. 2,4,6,8,10 (all these cannot be prime since they are a multiple of the prime number itself)
- Find the first number remaining on the list greater than p (this number is the next prime); let p equal this number.
- Repeat steps 3 and 4 until the prime number is greater than the square root of the number n (or where p2 > n)
- All the remaining numbers on the list are prime.
Example
To find all the prime numbers less than or equal to 30:
