StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>The Sieve of Eratosthenes works fine as illustrative way to find primes, but I would implement it a little bit different. The essence is that you don't have to check numbers which are multiples of already known primes. Now, instead of using an array to store this information, you can also create a list of all sequential primes up to the square root of the number you are checking, and then it suffices to go through the list of primes to check for primes.</p> <p>If you think of it, this does what you do on the image, but in a more "virtual" way.</p> <p><strong>Edit:</strong> Quickly hacked implementation of what I mean (not copied from the web ;) ):</p> <pre><code> public class Sieve { private readonly List<int> primes = new List<int>(); private int maxProcessed; public Sieve() { primes.Add(maxProcessed = 2); // one could add more to speed things up a little, but one is required } public bool IsPrime(int i) { // first check if we can compare against known primes if (i <= primes[primes.Count-1]) { return primes.BinarySearch(i) >= 0; } // if not, make sure that we got all primes up to the square of i int maxFactor = (int)Math.Sqrt(i); while (maxProcessed < maxFactor) { maxProcessed++; bool isPrime = true; for (int primeIndex = 0; primeIndex < primes.Count; primeIndex++) { int prime = primes[primeIndex]; if (maxProcessed % prime == 0) { isPrime = false; break; } } if (isPrime) { primes.Add(maxProcessed); } } // now apply the sieve to the number to check foreach (int prime in primes) { if (i % prime == 0) { return false; } if (prime > maxFactor) { break; } } return true; } } </code></pre> <p>Uses about 67ms on my slow machine.... test app:</p> <pre><code>class Program { static void Main(string[] args) { Stopwatch sw = new Stopwatch(); sw.Start(); Sieve sieve = new Sieve(); for (int i = 10000; i <= 100000; i++) { sieve.IsPrime(i); } sw.Stop(); Debug.WriteLine(sw.ElapsedMilliseconds); } } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload