High Speed Prime Numbers Calculation

Introduction

I spend a lot of time, making programs capable of coming out with a large collection of prime numbers, for any use.

Let�s assume all of you know what a prime number is. The usual way for programs to calculate a number of prime numbers is collecting prime numbers one number at the time, calculating the next prime number, adding it to the previous list.

• 2 Is prime number, because it�s divisible only by itself and 1.
• List is now {2}.
• 3 Is prime number, because it�s divisible only by itself and 1.
• List is now {2, 3}.
• 4 Is not a prime number, because it�s divisible by 2, the 0th item of the list.
• 5 Is prime number, because it�s divisible only by itself and 1.
• List is now {2, 3, 5}.
• 6 Is not a prime number, because it�s divisible by 2, the 0th item of the list.
• 7 Is prime number, because it�s divisible only by itself and 1.
• List is now {2, 3, 5, 7}.
• 8 Is not a prime number, because it�s divisible by 2, the 0th item of the list.
• 9 Is not a prime number, because it�s divisible by 3, the 1st item of the list.
• 10 Is not a prime number, because it�s divisible by 2, the 0th item of the list.
• And so on...

I�m not dividing the number 10 with other numbers whether they are or not prime number, because, there�s no use doing it. There�s no use on dividing a number by 2 and by 4, because 4 is 2 times 2, 6 is 2 times 3, and so on.

An appropriate algorithm to do this would be:

ArrayList primeNumbers = new ArrayList();

for(int i = 2; i < 100; i++)
{
    bool divisible = false;

    foreach(int number in primeNumbers)
        if(i % number == 0)
            divisible = true;

    if(divisible == false)
        primeNumbers.Add(i);
}

It works, and I do it fast. For each number for 2 to 100, it's dividing lots of times. If you are trying to get 100,000 prime numbers, the thing gets messy. But I am happy making my programs faster, improving its mechanisms, gaining in memory, writing them on assembler!, and that sort of things. But just then I found the The Sieve of Eratosthenes that made me open my eyes. This method, works as follows:

1. Write down the numbers 1, 2, 3, ..., n. We will eliminate composites by marking them. Initially all numbers are unmarked.
2. Mark the number 1 as special (it is neither prime nor composite). Set k=1. Until k exceeds or equals the square root of n, do this:
   1. Find the first number in the list greater than k that has not been identified as composite. (The very first number so found is 2.) Call it m.
   2. Mark the numbers 2m, 3m, 4m, ... as composite. (Thus in the first run, we mark all even numbers greater than 2. In the second run, we mark all multiples of 3 greater than 3.) m is a prime number. Put it on your list.
   3. Set k=m and repeat.
3. Put the remaining unmarked numbers in the sequence on your list of prime numbers.

You can try making this on your own. It�s really easier and faster. Because you�re not dividing, you are just jumping equal numbers of spaces.

So I figured, if this method makes it easier for me, what could it make for a machine!? I had all I needed, so I started programming it. I�ve had a sheet of paper (an ordered array of booleans), and the jumping action� the for() statement!!! The results were amazing. I�ve calculated the first 3,000,000,000 numbers and distinguished them into primes and composites in just 10 minutes! Something impossible with the previous algorithm. The only difficulty is that you will need a huge memory, to go over this number. Obviously, this method, consumes lots of memory, but it�s a great way of getting fast the first hundreds of millions of prime numbers. So, you can go on with some other algorithm, working on disk, or something like that.

So, no more preambles, here's the code:

using System.Collections;

int topNumber = 1000000;
BitArray numbers = new BitArray(topNumber, true);

for(int i = 2; i < topNumber; i++)
    if(numbers[i])
    {
        for(int j = i * 2; j < topNumber; j += i)
            numbers[j] = false;
    }

int primes = 0;

for(int i = 1; i < topNumber; i++)
    if(numbers[i])
    {
        primes++;
        //Console.Out.WriteLine(i);

    }

Console.Out.WriteLine();
Console.Out.WriteLine(primes + " out of " + topNumber + " prime numbers found.");
Console.In.ReadLine();

//Tnx Bistok for your help!

I would hardly recommend you that you do not uncomment the Console.Out.WriteLine line, it really slows it all down, and that�s not the point of all these.

If you have a good machine and you make it to calculate a really big number of primes, please let me know, and if any of you has any suggestions either.