factor_random_integers.py

# factor_random_integers.py

def randIntOfRandLength(minLength, maxLength):
    """
    First, the function generates a random length in closed interval
    [minLength, maxLength]. Then it generates a random integer n of that length,
    i.e., that many digits. The important feature of this function is that
    lengths within the max and min are all equally likely, as opposed to
    functions such as random.randint(). For example, for
    random.randint(10, 999), integers of 3-digit integers are 10 times more
    likely to be generated than 2-digit integers.
    """
    import random
    x = None
    s = ""
    n = None
    length = random.randint(minLength, maxLength)
    while True:
        x = random.randint(0, 9)
        s = s + str(x)
        if s[0] == '0':
            s.lstrip('0')
        n = int(s)
        if n >= 10**(length - 1):
            return n

def load_pickled_data(path='C:\P32Working\Data\primes_to_100_million.dat'):
    import pickle
    import os.path
    import io

    if os.path.getsize(path) == 0:
        #The file exists, but is empty: leave it alone
        pass

    elif os.path.exists(path):
        #The file exists and is not empty: use it
        with open(path, "rb") as f:
            data = pickle.load(f)
    print("That f is closed now is", f.closed)

    D = data
    primes = D
    return primes

def int_factors(n, primes):
    import gmpy2
    from gmpy2 import is_prime

    factors = []
    limit = int(n**.5) + 1
    if is_prime(n):
        return [int(n)]

    if n == 1:
        return []

    for x in primes:
        while n % x == 0:
            factors.append(int(x))
            n = n // x
            if is_prime(n):
                factors.append(int(n))
                return factors

    while True:

        x += 2

        while n % x == 0:
            factors.append(int(x))
            n = n // x
            if is_prime(n):
                factors.append(int(n))
                return factors

def test_of_list_of_prime_factors_of_int(n, list_):
    """
    Remains silent unless error detected.
    """
    import gmpy2
    from gmpy2 import is_prime

    error_flag = 0
    for e in list_:
        if type(e) != type(4):
            error_flag = 1
            print(c, "is not an integer!")
        elif not is_prime(e):
            error_flag = 1
            print(e, "is not prime!")
    if error_flag == 1:
        print("Not all elements of list of factors are prime! (n = ", n,")", sep='')
    product = 1
    for e in list_:
        product *= e
    if n != product:
        print("Product of factors doesn't equal n! (n = ", n,")", sep='')

def factor_random_integers(num_integers, min_length, max_length):
    from time import clock as t
    t0 = t()
    primes = load_pickled_data()
    t1 = t()
    for z in range(num_integers):
        n = randIntOfRandLength(min_length, max_length)
        t2 = t()
        factors = int_factors(n, primes)
        test_of_list_of_prime_factors_of_int(n, factors)
        t3 = t()
        print("Round ", z+1, " of ", num_integers, " (", len(str(n)),
              "-digit integer)", sep='')
        print(n, factors)
        print("factorization time + quality control time was", round((t3-t2),6))
        print()
    print("DONE")
    t11 = t()
    print("Time to load pickled data was", round((t1-t0),2))
    print("Total time for", num_integers, "integers was", round((t11-t0),2))

num_integers, min_length, max_length = 10, 8, 16

factor_random_integers(num_integers, min_length, max_length)

"""
EXAMPLE OUTPUT:

That f is closed now is True
Round 1 of 10 (15-digit integer)
301792625554978 [2, 150896312777489]
factorization time + quality control time was 0.201256

Round 2 of 10 (13-digit integer)
7668401194371 [3, 43, 79, 11699, 64319]
factorization time + quality control time was 0.00036

Round 3 of 10 (14-digit integer)
68840270075998 [2, 191, 1571, 114710459]
factorization time + quality control time was 0.000133

Round 4 of 10 (16-digit integer)
3140153631102584 [2, 2, 2, 31, 12661909802833]
factorization time + quality control time was 0.000102

Round 5 of 10 (14-digit integer)
48593145820843 [13, 23741, 157446371]
factorization time + quality control time was 0.0007

Round 6 of 10 (15-digit integer)
751404927012073 [109, 157, 43908427921]
factorization time + quality control time was 0.00011

Round 7 of 10 (8-digit integer)
33691448 [2, 2, 2, 7, 163, 3691]
factorization time + quality control time was 4e-05

Round 8 of 10 (12-digit integer)
653737274053 [31, 21088299163]
factorization time + quality control time was 7.3e-05

Round 9 of 10 (13-digit integer)
5235061190279 [179, 153611, 190391]
factorization time + quality control time was 0.003362

Round 10 of 10 (8-digit integer)
17769484 [2, 2, 19, 229, 1021]
factorization time + quality control time was 4.5e-05

DONE
Time to load pickled data was 0.75
Total time for 10 integers was 0.97

"""