Given a integer p > 1, if p can be devided only by 1 and itself, we say that p is a prime number. For example, 31 can only be devided by 1 and 31, so 31 is a prime number; 12 can be devided by six numbers: 1, 2, 3, 4, 6, 12, so 12 is not a prime number. The smallest ten prime number is 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.
Eratosthenes was a Greek mathematician, astronomer, and geographer. He invented a method for finding prime numbers that is still used today. This method is called Eratosthenes'Sieve. A sieve has holes in it and is used to filter out the juice. Eratosthenes's sieve filters out numbers to find the prime numbers. Eratosthenes's sieve can be used as follows to find all prime numbers smaller than or equal to a given number n: Step1 : Put all integers between 2 and n (include 2 and n) on Eratosthenes's sieve. Step2 : Sellect the smallest number on the sieve, suppose it is m, then m must be a prime. Step3 : Filter out all the integers which can be devided by m from Eratosthenes's sieve. Step4 : If m * m ≤ n, go to Step 2. Step5 : Integers remains on the sieve are all prime numbers. or example, if we want to find all primes between 2 and 20 using Eratosthenes's sieve,Put all integers between 2 and 20 on Eratosthenes's sieve. Sieve : 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 Prime bin : Sellect the smallest number, it's 2, so it is a prime. Then filter out all integers can be devided by 2: Sieve : 3, 5, 7, 9, 11, 13, 15, 17, 19 Prime bin : 2 Sellect the smallest number, it's 3, so it is also a prime. Then filter out all integers can be devided by 2: Sieve : 5, 7, 11, 13, 17, 19 Prime bin : 2, 3 Sellect the smallest number, it's 5, so it is also a prime. Then filter out all integers can be devided by 5: Sieve : 7, 11, 13, 17, 19 Prime bin : 2, 3, 5 Because 5 * 5 = 25 > 20, so all numbers remains on Eratosthenes's sieve are prime, put all of them into prime bin: Sieve : Prime bin : 2, 3, 5, 7, 11, 13, 17, 19 --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/javaprogrammingwithpassion?hl=en -~----------~----~----~----~------~----~------~--~---
