fac.py

#!/usr/bin/python
import random
import sys
"""
License BSD
swift navigation fizzbuzz question
mr-pirimality test from the internet
rest is coded by candidate.
./fac n
"""

#miller rabin
# Primality Testing with the Rabin-Miller Algorithm
# http://inventwithpython.com/hacking (BSD Licensed)
def is_probable_prime(num):
    s = num - 1
    t = 0
    if num < 2:
        return False
    if num % 2 == 0 and num != 2:
        return False
    while s % 2 == 0:
        # keep halving s while it is even (and use t
        # to count how many times we halve s)
        s = s // 2
        t += 1

    for trials in range(5): # try to falsify num's primality 5 times
        a = random.randrange(2, num - 1)
        v = pow(a, s, num)
        if v != 1: # this test does not apply if v is 1.
            i = 0
            while v != (num - 1):
                if i == t - 1:
                    return False
                else:
                    i = i + 1
                    v = (v ** 2) % num
    return True

def sieve(limit):
    tbl = [True] * limit
    tbl[0] = False
    tbl[1] = False
    primes = {}
    for i, v in enumerate(tbl):
        if v:
            primes[i] = i
            for n in xrange(i**2, limit, i):
                tbl[n] = False
    return primes

def genfib(n):
    a = 0
    b = 1
    if n <= 0:
        raise ValueError()
    else:
        for times in xrange(n):
            a, b = b, a+b
            yield a

def print_fb(n, cached_primes):
    if n % 3 == 0:
        print "Buzz"
    elif n % 5 == 0:
        print "Fizz"
    elif n % 15 == 0:
        print "FizzBuzz"
    elif n in cached_primes or is_probable_prime(n):
        print "BuzzFizz"
    else:
        print n


if __name__ == "__main__":
#for smaller primes upto SIEVE_LIMIT I use a cached dictionary of primes myself
#otherwise i switch algorithm to miller-rabin that I lifted off the internet
    SIEVE_LIMIT = 10000
    small_primes = sieve(SIEVE_LIMIT)
    try:
        for i in genfib(int(sys.argv[1])):
            print_fb(i, small_primes)
    except:
        pass