Jan 24 2010
Sieve (of Eratosthenes) algorithm for generating prime numbers
A prime number is divisible by 1 or by itself. To generate prime numbers to 20 we’ll use Sieve (of Eratosthenes) algorithm, which is really simple to explain:
Strike out all multiples of 2’s:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Strike out all multiples of 3’s:
2 3 5 7 9 11 13 15 17 19
And so on. Here is a C# code that does exactly that:
private static void PrintPrimesTo(int num) {
var primes = new bool[num + 1];
// init candidates
for (int i = 2; i <= num; i++) { primes[i] = true; }
// cross-out 2's:
// 2, 4, 6, 8, 10...
// cross-out 3's:
// 9, 12, 15...
for (int i = 2; (i * i) <= num; i++ ) {
Console.WriteLine("Crossing out {0}'s to {1}:", i, num);
for (int j = i * i; j <= num; j = j + i) {
Console.WriteLine(" * crossing-out: {0}", j);
primes[j] = false;
}
}
Console.WriteLine("Results: prime numbers between 2 and {0}:", num);
for (int i = 2; i <= num; i++) {
if (primes[i]) Console.WriteLine(" * {0} ", i);
}
}
Sample output from calling PrintPrimesTo(100):
Crossing out 2's to 20: * crossing-out: 4 * crossing-out: 6 * crossing-out: 8 * crossing-out: 10 * crossing-out: 12 * crossing-out: 14 * crossing-out: 16 * crossing-out: 18 * crossing-out: 20 Crossing out 3's to 20: * crossing-out: 9 * crossing-out: 12 * crossing-out: 15 * crossing-out: 18 Crossing out 4's to 20: * crossing-out: 16 * crossing-out: 20 Results: prime numbers between 2 and 20: * 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19
March 8th, 2010 at 10:14 pm
This is great – you can also create a single loop which ‘crosses out’ multiples of other primes up to quite a bit… by unrolling the loop and finding the pattern of multiples, which always repeats. Having a hard-coded loop which eliminates multiples turns out to be very performant as well… This is one aspect of my favorite interview question, how to determine if a number is prime? Lots of fun.
I once had a team challenge where everyone on the team implemented their own algorithm to see who could make the fastest prime detector.
The best part about this is that there are so many layers of the answer, it’s easy to talk about the problem at many levels and depths of optimization…
March 20th, 2010 at 10:52 pm
It’s funny I was just reading about this method this morning in the book “Mathematics from the birth of numbers”
September 3rd, 2011 at 5:00 am
http://www.wholesalehatsstore.com
Thanks to this blog I finally managed to find the information matching my criteria and for this I would like to thank the author for sharing this blog with us. Looking forward for more.
October 25th, 2011 at 1:14 am
What a good blog!!I like it very much.Thanks for sharing.caiyifang/comment201110
November 1st, 2011 at 2:19 pm
I totally agree with this article.
November 24th, 2011 at 3:52 am
cheap nike shox “Will be from eight pages copy books to 14 pages, when finish copy when back. If keep thinking about eating, I feel some early….
December 1st, 2011 at 9:48 am
The famous military monster beats
critics, the Air Force Command College Professor of strategy at, air vice-marshal Qiao Liang said,
December 5th, 2011 at 8:25 am
http://www.monclerkidoutlet.com/ cup, not too attention, but lost the game back after the team did not immediately allow players to go home, but together watch video, which in my opinion, is the effectiveness of Everton during only one. So it came to understand the FA Cup football in England component.”
January 7th, 2012 at 7:42 am
Somewhat more edgy than the active collection the models in the lifestyle collection have attitude, uninhibited styling and overwhelming appeal.discount mac cosmetics Serious eyewear that has superior optics and pioneering designs such as the legendary Oil Rig and Gascan,mac makeup wholesale models that will stay fresh with the latest fashions yet intense enough to stay different wholesale mac cosmetics.
January 7th, 2012 at 7:43 am
When planning your trip you need to remember range things beats by dre,I’ll be sure to come back. thanks for sharing beats studio.
January 15th, 2012 at 10:21 pm
[...] of sustainability in the constructed operating environment. SO let's use green electrical power!Alternative Energy : Have you ever run the dishwasher or washing machine when it was not completely…and even to go green as far as electrical energy is concerned. As an example: your dishwasher and [...]
January 31st, 2012 at 4:20 pm
Nice effort, very informative, this will help me to complete my task. Thanks for share it keep it up.