StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Sadly, I haven't tried the algorithmic approaches before. But if you want to implement your approach efficiently, I'd suggest doing some caching. Create an array to store all prime numbers less than a defined threshold, fill this array, and search within/using it.</p> <p>In the following example, finding whether a number is prime is O(1) in the best case (namely, when the number is less than or equal to <code>maxPrime</code>, which is 821,461 for a 64K buffer), and is somewhat optimized for other cases (by checking mod over only 64K numbers out of the first 820,000 -- about 8%).</p> <p>(Note: Don't take this answer as the "optimal" approach. It's more of an example on how to optimize your implementation.)</p> <pre><code>public static class PrimeChecker { private const int BufferSize = 64 * 1024; // 64K * sizeof(int) == 256 KB private static int[] primes; public static int MaxPrime { get; private set; } public static bool IsPrime(int value) { if (value <= MaxPrime) { return Array.BinarySearch(primes, value) >= 0; } else { return IsPrime(value, primes.Length) && IsLargerPrime(value); } } static PrimeChecker() { primes = new int[BufferSize]; primes[0] = 2; for (int i = 1, x = 3; i < primes.Length; x += 2) { if (IsPrime(x, i)) primes[i++] = x; } MaxPrime = primes[primes.Length - 1]; } private static bool IsPrime(int value, int primesLength) { for (int i = 0; i < primesLength; ++i) { if (value % primes[i] == 0) return false; } return true; } private static bool IsLargerPrime(int value) { int max = (int)Math.Sqrt(value); for (int i = MaxPrime + 2; i <= max; i += 2) { if (value % i == 0) return false; } return true; } } </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