Though a good answer has been accepted, and I've offered another answer previously, I offer a new method for ulong
that does things slightly different that may help explain why the 6 is important. This uses a for
loop rather than a while
.
UPDATE: I have expanded upon this answer with a version that runs in parallel threads. See this CodeReview Link for the parallel version.
Edit: added quick elimination of many composites
public static bool IsPrime6(ulong number)
{
// Get the quick checks out of the way.
if (number < 2) { return false; }
// Dispense with multiples of 2 and 3.
if (number % 2 == 0) { return (number == 2); }
if (number % 3 == 0) { return (number == 3); }
// Another quick check to eliminate known composites.
// http://programmers.stackexchange.com/questions/120934/best-and-most-used-algorithm-for-finding-the-primality-of-given-positive-number/120963#120963
if (!( ((number - 1) % 6 == 0) || ((number + 1) % 6 == 0)) )
{
return false;
}
// Quick checks are over. Number is at least POSSIBLY prime.
// Must iterate to determine the absolute answer.
// We loop over 1/6 of the required possible factors to check,
// but since we check twice in each iteration, we are actually
// checking 1/3 of the possible divisors. This is an improvement
// over the typical naive test of odds only which tests 1/2
// of the factors.
// Though the whole number portion of the square root of ulong.MaxValue
// would fit in a uint, there is better performance inside the loop
// if we don't need to implicitly cast over and over a few million times.
ulong root = (ulong)(uint)Math.Sqrt(number);
// Corner Case: Math.Sqrt error for really HUGE ulong.
if (root == 0) root = (ulong)uint.MaxValue;
// Start at 5, which is (6k-1) where k=1.
// Increment the loop by 6, which is same as incrementing k by 1.
for (ulong factor = 5; factor <= root; factor += 6)
{
// Check (6k-1)
if (number % factor == 0) { return false; }
// Check (6k+1)
if (number % (factor + 2UL) == 0) { return false; }
}
return true;
}
This is based on math theorem that states every prime number > 3 can be represented as (6k+/-1). But that doesn't mean every number of the form (6k+/1) is a prime.
The correct converse would be that if you have a number that is not represented as (6k+/-1) then that number cannot be prime.
For later use with modulo operator, (6k-1) is equivalent to (6(k+1)+5).
Thus our intent is to start the loop at 5, i.e. the first occurrence of (6k-1) for k=1, do checks inside the loop for (6k-1) and (6k+1), and then increment by 6 for another iteration through the loop.
In short, iterating by adding 6 to the previous factor is the same as adding 1 to k.
Explanation of Ugly Explicit Casts
I took out the UL
designators after further tests showed that for this algorithm they made little difference.
Tests
To run some tests, you could try:
const long Largest63bitPrime = 9223372036854775783L;
const ulong Largest64bitPrime = 18446744073709551557UL;
On my laptop, it take 13 seconds for the largest 63-bit prime, and 18 seconds for the largest 64-bit prime. Surprisingly, the version above is 1.5 seconds faster against (ulong)Largest63bitPrime
than using my other answer's long
specific version that employs a while
.
Quick Elimination of Many Composites
Based on comments to the OP itself, I added a new check. It’s kind of difficult to find the worst case scenario, or best time-savings case here. I tested it against Largest64bitPrime + 6
. Without the check, it was 14.2 microseconds compared to 1.1 microseconds with it. But's in now included so that the algorithm is considered complete.