The Big Programming Thread - Page 995

"""Returns True if n is prime."""
def isprime(n):
    if n <= 3 and n > 1:
        return True

    if n % 2 == 0 or n % 3 == 0:
        return False

    i = 5
    w = 2

    while i * i <= n:
        if n % i == 0:
            return False

        i += w
        w = 6 - w

    return True

public class PrimeSieve {
    private bool[] _notPrimes;
    private List<ulong> _primes = new List<ulong>();

    public PrimeSieve(ulong max) {
        SievePrimes(max);
    }

    private void SievePrimes(ulong max) {
        _notPrimes = new bool[max / 2 + 1];
        _primes.Add(2);
        for (ulong num = 3; num <= max; num += 2) {
            if (!_notPrimes[num / 2 - 1]) {
                _primes.Add(num);
                for (ulong composite = 3; composite * num <= max; composite += 2) {
                    _notPrimes[composite * num / 2 - 1] = true;
                }
            }
        }
    }

    public bool IsPrime(ulong num) {
        if (num <= 1) {
            return false;
        } else if (num == 2) {
            return true;
        } else if (num % 2 == 0) {
            return false;
        } else {
            return !_notPrimes[num / 2 - 1];
        }
    }

    public int Count {
        get { return _primes.Count; }
    }

    public IEnumerable<ulong> Enumerate {
        get { return _primes; }
    }
}