Spliting a prime number.

I know how to do it using the pari library

>>> from pari import factor
>>> x = 252
>>> g = factor(x, x)
>>> zip(*(eval(str(g[i])[:-1]) for i in (0,1)))
[(2, 2), (3, 2), (7, 1)]

Start with the smallest divisor, 2; see if it is a divisor and increase up to the square root + 1. So in this case
252 / 2 = 126
So 2 is a divisor. Then using 126 (divide by 2 up to square root 126 + 1)
126 / 2 = 63 -----> 2*2
Using 63
63 / 2 = False
63/3 is a divisor = 21
21 / 2 = False
21 / 3 = 7 (square root + 1 = 3)
and repeating the process yields no other divisors --> 1
You could use recursion for this, but I don't like recursion so would suggest a while loop. Come up with some code to start us off. I did a sloppy quick try using a while loop to call a function and came up with 25 lines of code.

You need not check already tested factors like 2. I would suggest for loop containing while and break out to quit the loop.

You need not check already tested factors like 2. I would suggest for loop containing while and break out to quit the loop.

Generator version of the function has 7 lines of code, list building version little more.;)

Well?? What happend to the code? Code to, say, find the lowest divisor to start?

Well?? What happend to the code? Code to, say, find the lowest divisor to start?

My quick and dirty solution, so I can delete this code.

def find_divisor(input_number):
    sq = int(input_number**0.5) + 1
    print("-->sq for %d = %d" % (input_number, sq))
    for ctr in range(2, sq+1):
        if 0 == input_number%ctr:
            return ((ctr, input_number/ctr))
    return((input_number, 1))

# 252 = 2*2 * 3*3 * 7*1
input_number = 252
divisors = []
found = True
while found:
    ## hey baby, nice pair (of numbers)
    smaller_1, larger_1 = find_divisor(input_number)
    print(smaller_1, larger_1)

    ## do again for the second (larger) number of the pair found
    if smaller_1 != input_number:      ## divisor found
        smaller_2, larger_2 = find_divisor(larger_1)
        print("     ", smaller_2, larger_2)
        divisors.append((smaller_1, smaller_2))
        input_number = larger_2     ## larger number of the 2nd pair
    else:              # no divisor=(original_number and 1)
        ## eliminate (1,1); a number like 6 will return (2, 3) and (1, 1)
        if smaller_1 != 1:    
            divisors.append((smaller_1, larger_1))
        found = False 
            
print(divisors)

OK, woooee, here is my code also

import random

def factors(value):
    if value > 3:
        for this in [2] + range(3,int(value ** 0.5)+1, 2):
            if this*this > value:  break
            while not (value % this):
                if value == this: break
                value /=  this
                yield this
    yield value

def power_factors(value):
    res = list(factors(value))
    return sorted((fact, res.count(fact)) for fact in set(res))

limit = 100000000
num = 10

for randval in (random.randint(1, limit) for count in range(num)):
    res = ' * '.join(str(x) for x in factors(randval))
    print ("factors of %i are: %s = %s" %  (randval, res, power_factors(randval)))
    assert eval(res) == randval

print('Factors and powers for 252: %s' % power_factors(252))

Any questions or code? Or is the case solved? If so, mark it solved.