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

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…

It’s funny I was just reading about this method this morning in the book “Mathematics from the birth of numbers”

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.

What a good blog!!I like it very much.Thanks for sharing.caiyifang/comment201110

I totally agree with this article.

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….

The famous military monster beats

critics, the Air Force Command College Professor of strategy at, air vice-marshal Qiao Liang said,

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.”