Pagina's

2011/01/16

Eratosthenes, part 2

// Primes can be written as 6*N-1 and 6*N+1,
// 5,7,11,13,17,19,23,25?29,.....
// Increase from prime to next prime:
// 2,4,2,4,2,4,2,4.....
// A table of indexes in the BitArray,
// and corresponding primes,
   
//  n prime
//   
//  0 5
//  1 7
//  2 11
//  3 13
//  4 17
//  5 19
//  6 23
//  7 25
//  8 29
//  9 31
// 10 35
// 11 37
// .. ..

// 25,35,55,65..have to be crossed off (in the BitArray).
// I had seen it somewhere, but didn't understand what was going on.
// Somewhere is:
   
// http://code.msdn.microsoft.com/factorialbenchmark/Release/ProjectReleases.aspx?ReleaseId=4516
   
// Result: it's ~20% faster, the BitArray is 33% smaller.

using System;
using System.Collections.Generic;
using System.Collections;
using System.Diagnostics;
class Program
{
    private static Stopwatch sw = new Stopwatch();
    static void Main()
    {
        int n = 1;
        while (n <= 1000000000)             // primes.exe n=10^9 18 s. 
        {
            sw.Restart();
            int[] primes = getPrimes(n);
            sw.Stop();
            Console.WriteLine("n: " + n + "  primes: " + primes.Length +
                              " in " + sw.ElapsedMilliseconds + " ms");
            n *= 10;
        }
        Console.ReadLine();
    }
    private static int[] getPrimes(int n)
    {
        if (n < 3)
        {
            if (n == 2) { int[] prime2 = { 2 }; return prime2; }
            else { int[] no_prime = { }; return no_prime; }
        }
        BitArray composite = new BitArray(n / 3);
        int d1 = 8, d2 = 8, p1 = 3, p2 = 7, s = 7, s2 = 3;
        int i = 0;
        int len = composite.Length;
        bool toggle = false;
        while (s < len)
        {
            if (!composite[i++])
            {
                int inc = p1 + p2;
                for (int k = s; k < len; k += inc)
                    composite[k] = true;
                for (int k = s + s2; k < len; k += inc)
                    composite[k] = true;
            }
            p1 += 2;
            if (toggle = !toggle)
            { s += d2; d1 += 16; p2 += 2; s2 = p2; }
            else
            { s += d1; d2 += 08; p2 += 6; s2 = p1; }
        }
        List<int> primes = new List<int>();
        double log_n = Math.Log(n);
        primes.Capacity = (int)((n / log_n) * (1 + 1.2762 / log_n));
        primes.Add(2); primes.Add(3);
        int p = 5;
        toggle = false;
        i = 0;
        while (p <= n)
        {
            if (!composite[i++]) primes.Add(p);
            p += (toggle = !toggle) ? 2 : 4;
        }
        return primes.ToArray();
    }
}

No comments:

Post a Comment