Click here to Skip to main content
15,867,453 members
Articles / Programming Languages / Visual Basic
Alternative
Article

Finding prime numbers

Rate me:
Please Sign up or sign in to vote.
4.67/5 (3 votes)
13 Sep 2012CPOL1 min read 26.4K   118   5   17
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 VersionThis Version
2,000,0007.7 ms3.14 ms
4,000,00016.41 ms7.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:

C#
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.

License

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


Written By
Software Developer (Senior) Retired
United States 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 (CE) systems.
After 35 years, Danaher having acquired Beckman (now Beckman Coulter), transferred the CE group to become part of Sciex (2014), and was on the software team that developed the new (9/2021) Sciex BioPhase Capillary Electrophoresis instrument.
---
Finally, after 43 years, 7 months, and 19 days, I am retired.

Comments and Discussions

 
SuggestionYou are just print the total founded prime number based on input range. Pin
Md. Marufuzzaman23-Dec-15 20:03
professionalMd. Marufuzzaman23-Dec-15 20:03 
You are just print the total founded prime number based on input range.
can you print all the prime number based on input range with best an efficient way.
Regards,
Md. Marufuzzaman

Questionjust a small trick Pin
Siavash _b13-Oct-12 11:37
Siavash _b13-Oct-12 11:37 
AnswerRe: just a small trick Pin
Matt T Heffron15-Oct-12 6:44
professionalMatt T Heffron15-Oct-12 6:44 
QuestionDoes it not belong to the alternate section of the orinigal version? Pin
Ankur\m/13-Sep-12 20:10
professionalAnkur\m/13-Sep-12 20:10 
AnswerRe: Does it not belong to the alternate section of the original version? Pin
Matt T Heffron14-Sep-12 6:49
professionalMatt T Heffron14-Sep-12 6:49 
QuestionWheel Factorization Pin
PIEBALDconsult13-Sep-12 17:22
mvePIEBALDconsult13-Sep-12 17:22 
AnswerRe: Wheel Factorization Pin
Matt T Heffron14-Sep-12 6:47
professionalMatt T Heffron14-Sep-12 6:47 
QuestionYou could make it even a bit faster Pin
Kenneth Haugland13-Sep-12 14:26
mvaKenneth Haugland13-Sep-12 14:26 
AnswerI got another ~7% Pin
Matt T Heffron14-Sep-12 8:00
professionalMatt T Heffron14-Sep-12 8:00 
GeneralRe: I got another ~7% Pin
Kenneth Haugland14-Sep-12 8:28
mvaKenneth Haugland14-Sep-12 8:28 
AnswerRe: I got another ~7% Pin
Matt T Heffron14-Sep-12 11:06
professionalMatt T Heffron14-Sep-12 11:06 
GeneralRe: I got another ~7% Pin
Kenneth Haugland14-Sep-12 11:30
mvaKenneth Haugland14-Sep-12 11:30 
GeneralRe: I got another ~7% Pin
Matt T Heffron14-Sep-12 12:04
professionalMatt T Heffron14-Sep-12 12:04 
GeneralRe: I got another ~7% Pin
Kenneth Haugland14-Sep-12 12:14
mvaKenneth Haugland14-Sep-12 12:14 
GeneralRe: I got another ~7% Pin
Matt T Heffron14-Sep-12 12:38
professionalMatt T Heffron14-Sep-12 12:38 
GeneralRe: I got another ~7% Pin
Kenneth Haugland14-Sep-12 12:49
mvaKenneth Haugland14-Sep-12 12:49 
GeneralRe: I got another ~7% Pin
Matt T Heffron14-Sep-12 12:51
professionalMatt T Heffron14-Sep-12 12:51 

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

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