Pagina's

2010/12/21

Primes, Sieve of Eratosthenes

// See Knuth's TAOCP section 4.5.4 exercise 8.
// The number of primes less then or equal to n: 
// http://primes.utm.edu/howmany.shtml 
// pi(n) <= n/ln(n)*(1+1.27262/ln(n))
// A fast sieve:
// http://www.primzahlen.de/files/referent/kw/sieb.htm
// (Pentium III 550 Mhz, C/C++, n=10^9, 2.533 s!)

using System;
using System.Collections;
using System.Collections.Generic;
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 23 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)
    {
        List<int> primes = new List<int>();
        if (n < 2) return primes.ToArray();
        double log_n = Math.Log(n);
        primes.Capacity = (int)((n / log_n) * (1 + 1.2762 / log_n));
        n = ((n & 1) + n) >> 1;
        BitArray x = new BitArray(n + 1);
        int i = 4, p = 3, q = 4;
        for (; q < n; q += p >> 1 << 2)
        {
            if (!x[q])
            {
                x[q] = true;
                for (i = q + p; i < n; i += p) x[i] = true;
            }
            p += 2;
        }
        primes.Add(2);
        for (i = 1; i < n; i++) if (!x[i]) primes.Add(i * 2 | 1);
        return primes.ToArray();
    }
}

1 comment:

  1. Even though Sieve of Atkin in theory should be faster than Sieve of Eratosthenes your implementation of the latter is much faster than mine of the former. I'm not surprised because I just did a naive translation from the pseudo code on Wikipedia to C#.

    Peter's impl. of The Sieve Of Eratosthenes
    n: 10000 primes: 1229 in 0 ms
    n: 100000 primes: 9592 in 2 ms
    n: 1000000 primes: 78498 in 20 ms
    n: 10000000 primes: 664579 in 213 ms
    n: 100000000 primes: 5761455 in 2744 ms
    n: 1000000000 primes: 50847534 in 33338 ms

    My impl. of The Sieve Of Atkin
    n: 10000 primes: 1229 in 3 ms
    n: 100000 primes: 9592 in 6 ms
    n: 1000000 primes: 78498 in 64 ms
    n: 10000000 primes: 664579 in 584 ms
    n: 100000000 primes: 5761455 in 7612 ms

    ReplyDelete