# pollard p-1
 
from fractions import gcd
 
def primes(n):
    ps = []
    sieve = [True] * n
    for p in range(2,n):
        if sieve[p]:
            ps.append(p)
            for i in range(p*p,n,p):
                sieve[i] = False
    return ps
 
def pminus1(n, b):
    c = 2
    for p in primes(b):
        pp = p
        while pp < b:
            c = pow(c, p, n)
            pp = pp * p
    g = gcd(c-1, n)
    if 1 < g < n:
        return g
    return 0
 
print primes(100)
print pminus1(87463, 120)

IyBwb2xsYXJkIHAtMQoKZnJvbSBmcmFjdGlvbnMgaW1wb3J0IGdjZAoKZGVmIHByaW1lcyhuKToKICAgIHBzID0gW10KICAgIHNpZXZlID0gW1RydWVdICogbgogICAgZm9yIHAgaW4gcmFuZ2UoMixuKToKICAgICAgICBpZiBzaWV2ZVtwXToKICAgICAgICAgICAgcHMuYXBwZW5kKHApCiAgICAgICAgICAgIGZvciBpIGluIHJhbmdlKHAqcCxuLHApOgogICAgICAgICAgICAgICAgc2lldmVbaV0gPSBGYWxzZQogICAgcmV0dXJuIHBzCgpkZWYgcG1pbnVzMShuLCBiKToKICAgIGMgPSAyCiAgICBmb3IgcCBpbiBwcmltZXMoYik6CiAgICAgICAgcHAgPSBwCiAgICAgICAgd2hpbGUgcHAgPCBiOgogICAgICAgICAgICBjID0gcG93KGMsIHAsIG4pCiAgICAgICAgICAgIHBwID0gcHAgKiBwCiAgICBnID0gZ2NkKGMtMSwgbikKICAgIGlmIDEgPCBnIDwgbjoKICAgICAgICByZXR1cm4gZwogICAgcmV0dXJuIDAKCnByaW50IHByaW1lcygxMDApCnByaW50IHBtaW51czEoODc0NjMsIDEyMCk=