#!/usr/bin/python
#
# Computing Prime Numbers, by Howdy Pierce.
# 
# Computes the prime numbers up to a limit using a C++ bitarray and a
# modified Sieve of Eratosthenes.
#
# For background, see the post http://cardinalpeak.com/blog?p=1172
#
# Copyright (c) 2012, Cardinal Peak, LLC.  http://cardinalpeak.com
#
# Redistribution and use in source and binary forms, with or without
# modification, are permitted provided that the following conditions
# are met:
# 
# 1) Redistributions of source code must retain the above copyright
#    notice, this list of conditions and the following disclaimer.
# 
# 2) Redistributions in binary form must reproduce the above
#    copyright notice, this list of conditions and the following
#    disclaimer in the documentation and/or other materials provided
#    with the distribution.
# 
# 3) Neither the name of Cardinal Peak nor the names of its
#    contributors may be used to endorse or promote products derived
#    from this software without specific prior written permission.
# 
# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
# "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
# LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
# FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
# CARDINAL PEAK, LLC BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
# SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
# LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
# USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
# ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
# OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
# SUCH DAMAGE.

import bitarray   # from http://pypi.python.org/pypi/bitarray/
import math
import sys

class Primes(object):
    def __init__(self, limit):
        """Build a bitarray where 0 indicates a composite and 1 indicates a prime"""
        self._primes = bitarray.bitarray(limit/2)

        self._primes.setall(True)
        self._primes[0] = False;

        sqrt_limit = math.sqrt(limit)

        i = 3
        while i < sqrt_limit:
            self._primes[i*i/2 : limit/2 : i] = False
            try:
                i = (self._primes.index(True, i/2 + 1)) * 2 + 1
            except ValueError:
                break


    def is_prime(self, n):
        """Returns True or False depending on whether the given number is prime"""
        if (n == 2): 
            return True

        if ((n % 2) == 0): 
            return False

        return self._primes[n/2]


def test(limit):
    p = Primes(limit)

    return

    for i in range(100):
        if (p.is_prime(i)):
            print i,

    print


def usage():
    print "Usage: primes limit num-repetitions"
    print "       This will calculate all primes up to the given limit."
    sys.exit(1)



if (len(sys.argv) != 3):
    usage()

limit = int(sys.argv[1])
reps = int(sys.argv[2])

if (limit == 0 or reps == 0):
    usage()

print "Calculating the primes up to %d (%d times)" % (limit, reps)

for i in range(reps):
    test(limit)