CODEWITHSUNDEEP
pythonfactorization
Nasif Imtiaz Ohi
Nasif Imtiaz Ohi

Reputation: 1713

factorization in python

this code is working fine. say for 1980 it gives the result 2 ^ 2 *3 ^ 2 *5 ^ 1 *7 ^ 0 *11 ^ 1 *(an extra asterisk remains at the end. i can remove it. and that has nothing to with my problem. the code is:

prime=[2,3,5]
f=7
def next_prime(f):
    j=0
    while j==0:
        for x in prime:
            if f%x==0:
                f+=2
                break
        else:
            j=1
    return f;
def factorization(n):
    list=[2,3,5]
    power=[]
    x=0
    while x<len(list):
        j=0
        while n%list[x]==0:
            j+=1
            n=n/list[x]
        power.append(j)
        x+=1
    if n!=1:
        while n!=1:
            g=next_prime(f)
            j=0
            while n%g==0:
                j+=1
                n=n/g
            else:
                power.append(j)
                prime.append(g)
    x=0
    while x<len(power):
        print(prime[x],"^",power[x],"*",end="")
        x+=1

factorization(1980)

then if i want to remove the term 7 ^ 0 from the result therefore all the primes which have the power zero, i made change in line 31 (if j!=0: instead of else:). and then the code's not working. it's working for numbers like 13860 where no prime has the power zero not in numbers like 1980. i can't find the problem! the changed code is:

prime=[2,3,5]
f=7
def next_prime(f):
    j=0
    while j==0:
        for x in prime:
            if f%x==0:
                f+=2
                break
        else:
            j=1
    return f;
def factorization(n):
    list=[2,3,5]
    power=[]
    x=0
    while x<len(list):
        j=0
        while n%list[x]==0:
            j+=1
            n=n/list[x]
        power.append(j)
        x+=1
    if n!=1:
        while n!=1:
            g=next_prime(f)
            j=0
            while n%g==0:
                j+=1
                n=n/g
            if j!=0:
                power.append(j)
                prime.append(g)
    x=0
    while x<len(power):
        print(prime[x],"^",power[x],"*",end="")
        x+=1

factorization(1980)

Upvotes: 1

Views: 325

Answers (3)

M C
M C

Reputation: 1

To add onto imsc's answer, There is actually an algorithm that uses loop =6 and loop +=6 then tries loop+1 and loop-1 that runs a little better. 2 & 3 must be tried manually first though.

Upvotes: 0

Alex Lokk
Alex Lokk

Reputation: 2116

I haven't analyzed your logic, but you're using else clause wrongly. while .. else makes sense only if you call a break inside your while. In your first code sample, the else branch is always executed.

As example, even the following code will run else branch:

while False:
    print 'while'
else:
    print 'else'

Upvotes: 2

imsc
imsc

Reputation: 7840

If you are only interested in getting the prime factors of a number you can try:

def primefactors(x):
    factorlist=[]
    loop=2
    while loop<=x:
        if x%loop==0:
            x/=loop
            factorlist.append(loop)
        else:
            loop+=1
    return factorlist

For example:

primefactors(1980)
[2, 2, 3, 3, 5, 11]
primefactors(13860)
[2, 2, 3, 3, 5, 7, 11]

Upvotes: 1

Related Questions