#!/usr/bin/env python

""" ------------------------------------------
 prime.py

 Classroom example for "Programming Workshop"
 illustrating documentation and tests.

 Returns the first prime number bigger than the number
 given as its argument.  For example,

    $ ./prime.py 20
    23

 This is designed for smallish inputs, and gives up if a prime isn't
 found within the next max_search integers; however, python
 understands converts automatically to arbitrarily large integers, and
 so will will do the right thing ... albeit slowly.
 
 Invoking it without arguments runs its tests.

 This program has at least two bug in it, even though it
 does the right thing when given 20 input.
 
 First, it doesn't pass all its tests.
   $ ./prime
    ...
    Failure in example: positive_integer()
    from line #5 of __main__.positive_integer
    Expected: False
    Got: 0
    ...
 
 * Exercise 1: Fix the program so that it *does* pass all tests.

 Second, this output is incorrect :
   $ ./prime 7
   8

 * Exercise 2:  Find the problem and fix it.
 * Exercise 3:  Add a test to make sure this problem doesn't happen again.

 Finally, the algorithm is pretty cruddy.

 * Exercise 4:  Which part is the bottleneck?  How do you know?
 * Exercise 5:  Find a better algorithm, and implement it. 

 copyright Jim Mahoney (mahoney@marlboro.edu)
 This code is open source under the GPL v2. 

 v 0.1, Jan 18 2006   initial (about 3 hours of work, mostly learning Python)
------------------------------------------- """

import sys
import math
import doctest

max_search = 1000       # Give up looking for a prime after input+max_search

def positive_integer(i=0):
    """Return i as a positive integer if it is, otherwise return False
    >>> positive_integer(7)
    7
    >>> positive_integer(' 13 ')
    13
    >>> positive_integer()
    False
    >>> positive_integer('a') or positive_integer(3.2)
    False
    """
    try:
        if int(i) == float(i) :
            return int(i)
        else :
            return False
    except:
        return False

def is_prime(x):
    """Return True if x is a prime integer.
    >>> is_prime(11)
    True
    >>> is_prime(16)
    False
    """
    # The implementation here is simplistic :
    # if any integer from 2 to sqrt(x) divides it, return false.
    # (Quick quiz : why only go up to sqrt(x) ?
    if not positive_integer(x):
        raise TypeError('not a positive integer')
    for i in range(2, int(math.sqrt(x))):
        if x % i == 0 :
            return False
    return True

def larger_prime(x):
    """Return the first prime larger than x.
    >>> larger_prime(20)
    23
    >>> larger_prime(37)
    41
    """
    # This implementation is even stupider than is_prime :
    # increment x until we find a number that's prime.
    # Give up and return False if we don't find one after max_search attempts.
    candidate = x+1
    while candidate < x + max_search :
        if is_prime(candidate) :
            return candidate
        else :
            candidate += 1
    return False

# ----- main --------------------------------------------------------------

if len(sys.argv) == 1 :
    doctest.testmod(verbose=True)
else :
    first_arg = sys.argv[1]           # What do you think sys.argv[0] is ?
    input_number = positive_integer( first_arg )
    if not input_number :
        print "Oops - '", first_arg , "' is not a positive integer."
        print "Usage: ./prime.py integer"
    else :
        answer = larger_prime( input_number )
        if not answer :
            print "Oops - no prime found between ", \
                  input_number, " and ", input_number + max_search
        else :
            print answer