Finding whether a number is Prime or not by limiting the number of iterations-c#

Question

I want to find whether a number is prime or not by limiting the number of iterations as much as possible.The following program was suggested in a blog.I can understand these parts of the code..

public static bool Isprime(long i)
    {
        if (i == 1)
        {
            return false;
        }
        else if (i < 4)
        {
            return true;
        }
        else if (i % 2 == 0)
        {
            return false;
        }
        else if (i < 9)
        {
            return true;
        }
        else if (i % 3 == 0)
        {
            return false;
        }

But I don't understand why f is incremented by 6.

else
        {
            double r = Math.Floor(Math.Sqrt(i));
            int f = 5;
            while (f <= r)
            {
                if (i % f == 0) { return false; }
                if (i % (f + 2) == 0) { return false; }
                f = f + 6;
            }
            return true;
        }  
    }

Answer 1

Because every prime number (except 2 and 3) is of the form 6k +/- 1 Every other number cannot be prime, because they are divisible by 2 or 3 Also, a few modifications to your method:

public static bool Isprime(long i)
{
    if (i < 2)
    {
        return false;
    }
    else if (i < 4)
    {
        return true;
    }
    else if ((i & 1) == 0)
    {
        return false;
    }
    else if (i < 9)
    {
        return true;
    }
    else if (i % 3 == 0)
    {
        return false;
    }
    else
    {
        double r = Math.Floor(Math.Sqrt(i));
        int f = 5;
        while (f <= r)
        {
            if (i % f == 0) { return false; }
            if (i % (f + 2) == 0) { return false; }
            f = f + 6;
        }
        return true;
    }  
}

• You didn't check for negative numbers
• To check if a number is even, (i & 1) == 0 is more efficient. Unfortunately, there is no such trick for i % 3

Answer 2

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.

Answer 3

See @Dennis_E's answer and explanation, which I gave +1. I offer 2 variations on his. There could be 100's of millions of implicit casts being done by these statements:

double r = Math.Floor(Math.Sqrt(i));
int f = 5;
while (f <= r)

The loop conditional implicitly cast f to a double repeatedly. That obscures where some performance can be degraded. While the whole number portion of the square root of long.MaxValue could fit in a uint, to boost performance you are better off keeping every as long. Now performance inside the loop will suffer from any implicit casts.

public static bool Isprime1(long number)
{
    // Get the quick checks out of the way.
    if (number < 2) { return false; }
    // 2 and 3 are prime.
    if (number < 4) { return true; }
    // besides 2, any other even number, i.e. any other multiple of 2, is not prime.
    if ((number % 2) == 0) { return false; }
    // 5 and 7 are also prime.
    if (number < 9) { return true; }
    // multiples of 3 are not prime.
    if (number % 3 == 0) { return false; }
    // Quick checks are over.  Must iterate to find the answer.
    // Though the whole number portion of the square root of long.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.
    long root = (long)Math.Sqrt(number);
    long factor = 5;
    while (factor <= root)
    {
        if (number % factor == 0L) { return false; }
        if (number % (factor + 2L) == 0L) { return false; }
        factor = factor + 6L;
    }
    return true;
}

All the above extends the answer by @Dennis_E. Another variation would be:

public static bool Isprime2(long number)
{
    // Get the quick checks out of the way.
    if (number < 2) { return false; }
    // 2, 3, 5, & 7 are prime.
    if ((new long[] { 2L, 3L, 5L, 7L }).Contains(number)) { return true; }
    // any other multiples of 2 are not prime.
    if ((number % 2) == 0) { return false; }
    // any other multiples of 3 are not prime.
    if (number % 3 == 0) { return false; }
    // Quick checks are over.  Must iterate to find the answer.
    // Though the whole number portion of the square root of long.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.
    long root = (long)Math.Sqrt(number);
    long factor = 5;
    while (factor <= root)
    {
        if (number % factor == 0L) { return false; }
        if (number % (factor + 2L) == 0L) { return false; }
        factor = factor + 6L;
    }
    return true;
}

Answer 4

public class Prime {
public static void main(String[] args) {
    Scanner get=new Scanner(System.in);
    int n;
    System.out.println("Enter a number to find its primality");
    n=get.nextInt();
    System.out.println(n+" isPRime? "+isPrime(Math.ceil(Math.sqrt(n)),n));
}
private static boolean isPrime(double n,int k){
  boolean isPrim=true;
  int p=(int)n;
  for(int i=2;i<=p;i++){
      boolean iprime=false;
      for(int j=2;j<i/2;j++){
          if(i%j==0){
              iprime=true;
              break;
          }              
      }
      if(!iprime && k>i){
          if(k%i==0){
              isPrim=false;
              return isPrim;
            }
         }
       }
  return isPrim;
}
}