13,250,029 members (63,356 online)
Alternative Article
alternative version

#### Stats

14.8K views
4 bookmarked
Posted 13 Sep 2012

# Finding prime numbers

, 13 Sep 2012
 Rate this:
This is an alternative for "Finding prime numbers"

## Introduction

This is an even faster and more space efficient variation on the implementation for finding prime numbers using Sieve of Eratosthenes.

## Background

We know that all even numbers greater than 2 are not prime, so remove them from the sieve process a priori.

## Using the code

Like the Clifford Nelson version, I used a simple array of Boolean for numbers. However, numbers are not represented directly. The boolean at index `n` represents the number `2n+1` (for `n > 0`). So, the array can be half the size of the previous version. My timings show this to be about twice as fast.

 Primes up to: Previous Version This Version 2,000,000 7.7 ms 3.14 ms 4,000,000 16.41 ms 7.00 ms

The attached file has the code with both versions, for calculating the timings.

This code below is just the new implementation. Just copy and paste it into a console app:

```class Program  {    private const int repeats = 1000;  // to get more significant timing    private const int rawCount = 2000000;    private const int initStart = 1;    private const int count = 1 + (rawCount - 1) / 2; // 1+ because rawCount-1 just might be prime    private static readonly int countLimit = (((int)Math.Sqrt(rawCount)) - 1) / 2;    private static bool[] _numbers = new bool[count];    static void Main(string[] args)    {      var sw = new System.Diagnostics.Stopwatch();      for (int j = 0; j < repeats; j++)      {        // I excluded initializing the _numbers array from the timing.        for (int i = initStart; i < count; i++)        {          _numbers[i] = true;        }        sw.Start();        Run2();        sw.Stop();      }      Console.WriteLine("Milliseconds/run: {0:F2}", sw.ElapsedMilliseconds/(double)repeats);      // The 1+ of the count is because 2 is assumed to be prime and is not represented in the array.      Console.WriteLine((1 + _numbers.Count(i => i)) + " primes < " + rawCount);      Console.ReadLine();    }    private static void Run2()    {      int baseCounter = 0;      int increment;      int index;      while (baseCounter < countLimit)      {        do        {          baseCounter++;          if (baseCounter == count)            return;        } while (!_numbers[baseCounter]);        increment = (baseCounter << 1) + 1;        index = baseCounter + increment;        while (index < count)        {          _numbers[index] = false;          index += increment;        }      }    }  }
```

## Points of Interest

I wondered if it would be possible to assume other small prime factors in the sieve and further reduce the array size? I convinced myself that it is not, since there are prime pairs that differ by two (such as 11 & 13) so any further compression of the sieve array would not be possible (at least for the Sieve of Eratosthenes).

Strangely, both versions exhibit significant slowdown when the size of the sieve array exceeds about 6MB.

This improvement of the sieve is not new! Search Code Project for "Eratosthenes" and you'll find many implementations. Some (probably most) use this type of optimization.

There are other faster methods of finding prime numbers in order, especially for large values, see Sieve of Atkin [^].

## History

9/13/2012 - Initial posting of the Alternative.

## Share

 Software Developer (Senior) Sciex United States
I started programming in Basic on a DECSystem-10 as a Freshman at Caltech in 1974. I quickly transitioned to assembly language, Fortran, and Pascal. As a summer job at JPL, I did analysis of fuel consumption for the Viking Mars Orbiter attitude control system. I also spent a summer doing O/S maintenance at Digital Equipment Corporation.
After graduation, I started developing microprocessor development tools (e.g., cross-compiler, debugger) for Beckman Instruments, a scientific instrument company.
I've worked on custom file-systems, a real-time O/S for Z8000, Expert Systems (SpinPro & PepPro), and internal and external networking support (I was their first webmaster).
I've worked on the DNA analysis system.
I was the console/UI software architect for Ultracentrifuges and protein Capillary Electrophoresis systems.
After 35 years, Danaher having acquired Beckman (now Beckman Coulter), transferred the CE group to become part of Sciex (2014).

## You may also be interested in...

 First Prev Next
 You are just print the total founded prime number based on input range. Md. Marufuzzaman23-Dec-15 21:03 Md. Marufuzzaman 23-Dec-15 21:03
 just a small trick Siavash _b13-Oct-12 12:37 Siavash _b 13-Oct-12 12:37
 Re: just a small trick Matt T Heffron15-Oct-12 7:44 Matt T Heffron 15-Oct-12 7:44
 Does it not belong to the alternate section of the orinigal version? Ankur\m/13-Sep-12 21:10 Ankur\m/ 13-Sep-12 21:10
 Re: Does it not belong to the alternate section of the original version? Matt T Heffron14-Sep-12 7:49 Matt T Heffron 14-Sep-12 7:49
 Wheel Factorization PIEBALDconsult13-Sep-12 18:22 PIEBALDconsult 13-Sep-12 18:22
 Re: Wheel Factorization Matt T Heffron14-Sep-12 7:47 Matt T Heffron 14-Sep-12 7:47
 You could make it even a bit faster Kenneth Haugland13-Sep-12 15:26 Kenneth Haugland 13-Sep-12 15:26
 I got another ~7% Matt T Heffron14-Sep-12 9:00 Matt T Heffron 14-Sep-12 9:00
 Re: I got another ~7% Kenneth Haugland14-Sep-12 9:28 Kenneth Haugland 14-Sep-12 9:28
 Hmm. This is some conunderum for me. I took your code and added the _numbers[i] = true to fit the function I build, meaning your code modefied like this: ```private static void Run2() {   for (int i = 0; i < _numbers.Count() - 1; i++) _numbers[i] = true;   // For the sake of comments, I'll use "bcn" to mean the number represented by baseCounter // I.e. bcn = 2 * baseCounter + 1 int baseCounter = 0; int increment; int index;   while (baseCounter < countLimit) { do { baseCounter++; if (baseCounter == count) return; } while (!_numbers[baseCounter]);   // we increment by 2*bcn since bcn is odd and odd+odd=even and even numbers are not there! increment = (baseCounter << 1) + 1; // this equals bcn, but "represents" 2*bcn //Since all products of bcn with multiples of smaller primes have already been removed // by the sieving process of those numbers, the smallest number to remove is at bcn^2 index = baseCounter * (increment + 1); while (index < count) { _numbers[index] = false; index += increment; } } }``` And compared that to this: ```/// /// Returns all the primes from 2 up to N /// /// Find all primes below N /// Improvments stems from the alternative article by Clifford Nelson, and my own improvments using his function /// private List SieveOfEratosthenes(int N) { //Stores all the prime numbers var result = new List(); int N1 = N - 1;   if (!(int.MaxValue > N)) { throw new IndexOutOfRangeException(String.Format("Span is too large for the array, pick a smaller range that does not exceed int.MaxValue")); }   //We need an boolean array that indicates if the number is a prime var IsPrime = new bool[N1];   //Fill the array with all true values and we will start at the number 0 //This is to avoid adding later values +2 when creating the list of primes for (int i = 0; i < N1-1; i++) { IsPrime[i] = true; }   //Find and store how many numbers we need to check int NumberOfPrimeChecks = (int)Math.Sqrt(N1);   //Start checking at the number 2, but we are adding 1 to start with so we set it at 1 int CurrentNumber = 1;   //Loop through all the nessecary checks while (CurrentNumber < NumberOfPrimeChecks) { do { CurrentNumber++; } while (!IsPrime[CurrentNumber]);   int counter = CurrentNumber << 1; while (counter < N1) { IsPrime[counter] = false; counter += CurrentNumber; } }   for (int i = 2; i < N1; i++) if (IsPrime[i]) result.Add(i);   return result;   }``` And on average your code was twice as slow as mine, so either Im doing something strange (meaning wrong) or its just faster. Like to know what results you got, but my function also returns a list of primes and if I excluded that Im sure I could cut the time in half at least.
 Re: I got another ~7% Matt T Heffron14-Sep-12 12:06 Matt T Heffron 14-Sep-12 12:06
 Re: I got another ~7% Kenneth Haugland14-Sep-12 12:30 Kenneth Haugland 14-Sep-12 12:30
 Re: I got another ~7% Matt T Heffron14-Sep-12 13:04 Matt T Heffron 14-Sep-12 13:04
 Re: I got another ~7% Kenneth Haugland14-Sep-12 13:14 Kenneth Haugland 14-Sep-12 13:14
 Re: I got another ~7% Matt T Heffron14-Sep-12 13:38 Matt T Heffron 14-Sep-12 13:38
 Re: I got another ~7% Kenneth Haugland14-Sep-12 13:49 Kenneth Haugland 14-Sep-12 13:49
 Re: I got another ~7% Matt T Heffron14-Sep-12 13:51 Matt T Heffron 14-Sep-12 13:51
 Last Visit: 31-Dec-99 19:00     Last Update: 19-Nov-17 12:17 Refresh 1