Click here to Skip to main content
Click here to Skip to main content

Prime Number Determination Using Wheel Factorization

, 2 Feb 2009 CPOL
Rate this:
Please Sign up or sign in to vote.
Determine if an integer is prime, and use Wheel Factorization to improve the algorithm.

PrimeSuspectProgram

Introduction

For a positive integer n, we have to determine if n is prime, where n is small (i.e., it can be assigned to a ulong type in C#). Thus, n will be constrained to be less than 2^64-1. The algorithm presented here will make some notable improvements over the brute force method by using Wheel Factorization.

Background

Prime numbers are interesting numbers to the math community. And, the search for prime numbers seems to be the hobby (or profession) of many mathematicians. Prime numbers are also important in the RSA encryption algorithm. There is even a prize money for finding very large primes.

The Algorithm

Our goal is to determine if a positive integer is prime or not. The brute force way would look something like this:

// Warning: Slow code ahead, do not use.
// The brute force way of determining if a number is prime.
public bool IsPrime(ulong primeSuspect)
{
    if (primeSuspect < 2) return false;

    if (primeSuspect == 2) return true;

    for (ulong divisor = 2; divisor < primeSuspect; divisor++)
    {
        // If no remainder after dividing by the divisor
        if (primeSuspect % divisor == 0) 
        {
           return false;  // It is not prime
        }  
    }
    // If we did not find a divisor, it is prime
    return true; 
}

The above code is inefficient because it often checks a number as a possible divisor that has already been eliminated because it is a multiple of a smaller number. No need to check 4 as a divisor if 2 was already checked. And, no need to check 9 as a divisor if 3 has already been checked, and so on. Another problem is that it checks all numbers up to our prime candidate as a divisor. We will fix this first.

So, our first improvement to the algorithm will be to only search for factors for our prime candidate up to the square root of our prime candidate. If there is a factor to our candidate greater than its square root, then there must also be a factor less than its square root such that when these two factors are multiplied, it gives us our original candidate.

Our next improvement will be to use a method called Wheel Factorization. If we already know all the primes less than or equal to the square root of our candidate, this would be optimal. However, searching for all these lesser primes comes at the price of more computation time, and negates much of our gains. So, I'll use Wheel Factorization to speed up the search.

In Wheel Factorization, you start with the first few primes. In this example, I will use 2, 3, and 5, the first three primes, to make it simple. (In the downloaded code, I use more than the first three primes, which will give us some more improvement.) This gives us a Wheel Factorization of 30, the product of the first three primes (2*3*5). You then make a list of the integers from 1 to 30, and eliminate all the numbers in the list that are multiples of 2, 3, or 5. This gives us this list: {1, 7, 11, 13, 17, 19, 23, 29} of sieved numbers. These sieved numbers give us a pattern of numbers that repeat and are not multiples of 2, 3, or 5. Thus, if you add 30, or 60, or 90, etc. to each of these numbers in the list, none are divisible by 2, 3, or 5. I will make a small modification to this sieved list of numbers to make the loop simpler. I will remove the 1, and add it to 30 at the tail of the list. So now, our list of numbers is {7, 11, 13, 17, 19, 23, 29, 31}. This is so I can do a pass = 0 and don't have to divide by 1.

So, here is the heart of the program (simplified for this article by using just the first three primes to create the sieve):

private static ulong[] aSieve30 = new ulong[]
         {7, 11, 13, 17, 19, 23, 29, 31};

// Find the first divisor greater than 1 of our candidatePrime.
public static ulong FirstDivisor(ulong candidatePrime)
{
    if (candidatePrime == 0)
        throw new ArgumentException ("Zero is an invalid parameter!");

    // A List of the first three primes
    List<ulong> firstPrimes = 
           new List<ulong>(new ulong[] {2, 3, 5}); 

    WheelFactor = 30;  // The product of the primes in firstPrimes

    if (candidatePrime == 1)
    {  
        // 1 is not considered a prime or a composite number.
        return 0; // So return any number other than 1.
    }
    foreach (ulong prime in firstPrimes)
    {
        if (candidatePrime % prime == 0) return prime;
    }

    // No need to search beyond the square root for divisors
    ulong theSqrt = (ulong)Math.Sqrt((double)candidatePrime); 

    for (ulong pass = 0; pass < theSqrt; pass += WheelFactor)
    {
        foreach (ulong sieve in aSieve30)
        {
            if (candidatePrime % (pass + sieve) == 0)
            {
                  return pass + sieve;
            }
        }
    }
    // If we got this far our number is a prime
    return candidatePrime;
}

public static bool IsPrime(ulong primeSuspect)
{
   if (primeSuspect == 0) return false;
   return (FirstDivisor(primeSuspect) == primeSuspect);
}

As you can see from the for loop above, it is incremented by our WheelFactor, which is 30 in this case. And, the inner loop checks all 8 primes in our sieved list. Therefore, just 8 of 30 numbers are checked, which is more than a 73% improvement over the brute force way. Unfortunately, increasing the number of primes in our first primes list has a diminishing improvement on our search. The downloaded code uses the first 8 primes, which gives about an 83% improvement over the brute force way.

WheelFactor.jpg

The figure illustrates a wheel factorization of 30. After performing trial divisions of 2, 3, and 5, then you only have to do trial divisions for those spokes of the wheel that are white. The spokes of the wheel that are red have been eliminated for consideration as possible divisors.

Conclusion

In Wheel Factorization, you get some good performance improvement in determining if a number is prime by skipping all the multiples of the first few primes.

Reference

History

  • 19 Nov 2008 - Original submission
  • 31 Jan 2009 - The BuildSieve() method was improved

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

rickoshay
Software Developer
United States United States
My name is Rick Oden. I am a software developer living in Colorado. I have been developing code for various companies for more than 19 years. The languages I have used includes Pascal, Visual Basic, Delphi, Plex, C#, and now looking into F#.

Comments and Discussions

 
NewsBenchmark Pinmemberrickoshay7-Dec-08 13:01 
I decided to run my own benchmarks against the Prime Suspect program to show the different performance levels at the different Wheel Factor values. I did not include in my timings the time it took to build the sieve list. This is because the sieve list is built once when the program initiates and remains in memory throughout the life of the program. I also modified the Brute Force method above to stop after reaching the square root of the prime number candidate. This is so that the benchmark would only show the effect of adding the wheel factorization to the algorithm. The brute force method is shown in the row with the # Primes in firstPrimes of zero.
All tests used the largest prime that can fit into a ulong field in C#, which is the default value of the demo program above. The times are listed in milliseconds and is the average of 5 tests. The computer used for the test is a Dell DIMENSION 8400 3.40 GHz and 1.00 GB of RAM. (Your results may vary.)
 
# Primes in          Time (ms)       Theoretical %      Actual % of
firstPrimes                          of Brute Force     Brute Force
-------------------------------------------------------------------
   0                 190220.4
   1                 130388.4             50.00%           68.55%
   2                  82826.0             33.33%           43.54%
   3                  65491.2             26.67%           34.43%
   4                  54261.8             22.85%           28.53%
   5                  49065.4             20.78%           25.79%
   6                  45318.0             19.18%           23.82%
   7                  42794.6             18.05%           22.50%
   8                  40594.6             17.10%           21.34%
   9                  39994.2             16.36%           21.03%
 

Some observations on the results:
 
Because of some additional overhead in the Wheel Factorization inner loop (the foreach loop) and the addition in the inner loop (pass + sieve) the actual gains do not quite meet the theoretical gains. But they get closer with more primes in the firstPrimes list.
 
Also note that the gains from row 8 to row 9 are small. This seems to be because the wheel factor for row 9 is over 223 million. So it may do millions of divisor checks before the code to check if it is over the square root of the candidate is executed.
GeneralEfficency of brute force [modified] Pinmembermurti38624-Nov-08 21:46 
GeneralRe: Efficency of brute force [modified] PinmemberMember 63015025-Nov-08 0:04 
AnswerRe: Efficency of brute force Pinmembermurti38625-Nov-08 0:54 
GeneralRe: Efficency of brute force (with is eqivalent to wheelfaktor 2) Pinmemberghard6826-Nov-08 9:07 
GeneralRe: Efficency of brute force Pinmemberrickoshay26-Nov-08 17:58 
GeneralRe: Efficency of brute force Pinmembermurti38626-Nov-08 21:29 
NewsBenchmark [modified] Pinmemberghard6827-Nov-08 7:16 
GeneralRe: Benchmark Pinmemberrickoshay27-Nov-08 8:48 
GeneralRe: Benchmark Pinmemberghard6828-Nov-08 6:38 
GeneralRe: Benchmark [modified] Pinmemberghard6827-Nov-08 13:29 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web03 | 2.8.141216.1 | Last Updated 2 Feb 2009
Article Copyright 2008 by rickoshay
Everything else Copyright © CodeProject, 1999-2014
Layout: fixed | fluid