0

Hi,

I need two functions one that checks if the inputed number is a prime
number and second one that splits the given number in to prafactors.

I have the first function done but the second one is a bit annoying.

The function has to take the given number and split it and save the results
in a list. Needs to split the prime number on factors and append that to an
empty list. Example:

252=2(on 2) * 3(on 2) * 7(on 1) - Because 2*2 * 3*3 * 7*1 = 256

And then i have to print this list in the following way:
[(2, 2), (3, 2), (7, 1)]

Edited by n3red: n/a

4
Contributors
8
Replies
9
Views
7 Years
Discussion Span
Last Post by pyTony
1

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)]
0

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.

Edited by woooee: n/a

0

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

Edited by pyTony: n/a

0

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.;)

0

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)

Edited by woooee: n/a

0

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))

Edited by pyTony: reduce dubug left overs

This question has already been answered. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.