Python prime factor decomposition

Generate prime factorisations of factorial numbers

The code was written to generate the factorisation of numbers into primes in ascending order. E.g 3! =’2 * 3′, 4!=’2^3 * 3′. When I have huge numbers such as 100!, the run time becomes a problem. I want to have a code which will run in less time.

from math import floor,sqrt,factorial from decimal import Decimal def prime(x): if x==2 or x==3 or x==5: return True if (x%2==0) or (x%3==0) or (x%5==0) or (x==1): return False for i in range(6,floor(sqrt(x)),6): if x%(i+1)==0: return False elif i%(i+5)==0: return False return True def decomp(n): y=factorial(n) if y;b=0 for i in pri: while y%i==0: y=y//i b+=1 a[i]=b b=0 if len(list(a.keys()))==1: if list(a.values())!=[1]: c=str(a.keys())+'^'+str(a.values()) else: c=str(list(a.keys())) elif len(list(a.keys()))>1: if a[list(a.keys())[0]]>1: c=str(list(a.keys())[0])+'^'+str(a[list(a.keys())[0]]) elif a[list(a.keys())[0]]==1: c=str(list(a.keys())[0]) for key in list(a.keys())[1:]: if aPython prime factor decomposition!=1: c+=' * '+str(key)+'^'+str(aPython prime factor decomposition) elif aPython prime factor decomposition==1: c+=' * '+str(key) return c 

2 Answers 2

Given that you do y=factorial(n) inside your decomp(n) function, I’m gonna assume that this is really about factoring factorials. And my review is gonna be:

• Don’t compute the factorial at all.
• Use a better function name.
• Document what the function does.
• Separate the factorization from the presentation. Return something more useful than a string, like pairs of primes and their exponents. That can then be pretty-formatted if desired, or used for computations.
• Test your code, because for example for decomp(10) returns ‘2 * 3 * 5 * 7’ , missing the exponents.

Instead of computing the factorial and then factoring that, factor all the numbers from 1 to n and combine their prime factorizations. Or even better. compute, for every prime from 1 to n, its exponent in n!. Let’s say we want to find the exponent for 3 in 100!. Every third number from 1 to 100 (i.e., 3, 6, 9, 12, etc) contributes a factor 3, so there are \$\lfloor\frac\rfloor=33\$ numbers that contribute factor 3. Of those, every third number (i.e., 9, 18, 27, etc) contributes another factor 3. Of those, every third number (i.e., 27, 54 and 81) contributes yet another. And 81 even contributes a fourth. So the exponent for 3 in 100! is 33+11+3+1=48.

Here’s an O(n) solution doing that. Takes my laptop about 0.33 seconds to factor 1,000,000!. Compare that to just computing math.factorial(10**6) , which already takes about 10 seconds.

def factorial_factorization(n): """Return the prime factorization of n! as list of (prime, exponent) pairs.""" # Compute primes from 2 to n, see https://cp-algorithms.com/algebra/prime-sieve-linear.html lp = [None] * (n+1) primes = [] for i in range(2, n+1): if not lp[i]: primes.append(i) lp[i] = i for p in primes: if p > lp[i] or i * p > n: break lp[i * p] = p # Find prime exponents for n! result = [] for p in primes: e = 0 m = n // p while m: e += m m //= p result.append((p, e)) return result 

>>> factorial_factorization(3) [(2, 1), (3, 1)] >>> factorial_factorization(4) [(2, 3), (3, 1)] >>> factorial_factorization(100) [(2, 97), (3, 48), (5, 24), (7, 16), (11, 9), (13, 7), (17, 5), (19, 5), (23, 4), (29, 3), (31, 3), (37, 2), (41, 2), (43, 2), (47, 2), (53, 1), (59, 1), (61, 1), (67, 1), (71, 1), (73, 1), (79, 1), (83, 1), (89, 1), (97, 1)] >>> factorial_factorization(10**6)[:10] [(2, 999993), (3, 499993), (5, 249998), (7, 166664), (11, 99998), (13, 83332), (17, 62497), (19, 55553), (23, 45453), (29, 35713)] 

If you want a less useful but prettier presentation, that’s easy to do then:

>>> n = 42 >>> print(f'! =', ' * '.join(f'
^' if e > 1 else f'
' for p, e in factorial_factorization(n))) 42! = 2^39 * 3^19 * 5^9 * 7^6 * 11^3 * 13^3 * 17^2 * 19^2 * 23 * 29 * 31 * 37 * 41 

>>> s = '2^39 * 3^19 * 5^9 * 7^6 * 11^3 * 13^3 * 17^2 * 19^2 * 23 * 29 * 31 * 37 * 41' >>> (result := eval(s.replace('^', '**'))) 1405006117752879898543142606244511569936384000000000 >>> (expect := math.factorial(42)) 1405006117752879898543142606244511569936384000000000 >>> result == expect True 

Источник

Prime Factorization | How to Find Prime Factors of a Number in Python

In this article, we will see a python program to print all the prime factors of the given number. If a number is a prime number and perfectly divides the given number then that number is said to be a prime factor of the given number. Here, we will see what is a prime factor, a method to find a prime factor, and the python program.

What is a prime factor of a number?

Prime factors of a number are the prime number which on multiplying together gives the number. we can check the prime factor of a number by two conditions:

Steps to find the prime factors of a number

1. Let the number be denoted by num.
2. while num is divisible by 2, we will print 2 and divide the num by 2.
3. After step 2, num must be always odd.
4. Start a loop from I = 3 to the square root of n. If i divide num, print i, and divide num by i. After i fail to divide num, increment the i value by 2 and continue.
5. If num is a prime number and is greater than 2, then the num cannot become 1.
6. So, print num if it is greater than 2.

Examples of Printing the Prime Factors of a Number in Python

Let us understand the program for prime factors of the number in details with the help of different examples:

1. Prime Factor of a number in Python using While and for loop

In this program, We will be using while loop and for loop both for finding out the prime factors of the given number. we will import the math module in this program so that we can use the square root function in python. After that, we will apply the loop and try to find the prime factors of the given number.

# python program to print prime factors import math def primefactors(n): #even number divisible while n % 2 == 0: print (2), n = n / 2 #n became odd for i in range(3,int(math.sqrt(n))+1,2): while (n % i == 0): print (i) n = n / i if n > 2: print (n) n = int(input("Enter the number for calculating the prime factors :\n")) primefactors(n)

Enter the number for calculating the prime factors : 650 2 5 5 13

Explanation:

Here firstly we have imported the math library from the python module. Secondly, we have taken the input n as the number and called the function primefactors(). Thirdly, we have taken primefactors() as the function and applied while loop and checked if the modulo of the number is coming 0 by dividing it by 2. Fourthly, the while loop will be executed till the number is even and divisible by 2 and printing it and divide the number by 2 at each iteration. After that, we will apply the for loop from ‘i=3’ till the square root of n+1. Then again we will apply while loop inside the for loop and check the condition. At last, if n is greater than 2 then we have printed the number. Hence, all the prime factors of the number get printed.

2. using for loop only

In this program, We will be using for loop only for finding out the prime factors of the given number. we will be applying multiple for loops and try to find the prime factors of the given number.

#using for loop n = int(input("Enter the number for calculating the prime factors :\n")) for i in range(2,n + 1): if n % i == 0: count = 1 for j in range(2,(i//2 + 1)): if(i % j == 0): count = 0 break if(count == 1): print(i)

Enter the number for calculating the prime factors : 350 2 5 7

Explanation:

In this example, we will be using for loop only. Firstly, we have taken the input from the user as n. Secondly, we have applied the for loop from i=2 to i=n+1. Then, we will check if the modulo of the value of i and number is equal to 0. Then we keep the count value = 1 and again apply the for loop inside the for loop from j=2 to j=i//2+1. and check the given if condition. if the condition satisfies count value is set to 0 and we break the statement. We come out of the for loop and check the condition if count ==1 and print the value of i. hence the primefactors are printed with the single-single value of them.

NOTE: Suppose we take input as 650 : the prime factors are 2,5,5,13 so, it will print 2,5,13 as all integers one time. 

3. Prime Factor Of A Number In Python using while loop only

In this program, We will be using a while loop only for finding out the prime factors of the given number. we will be applying multiple while loops and try to find the prime factors of the given number.

#using while loop n = int(input("Enter any Number for calculating the prime factors: ")) i = 1 while(i 
Enter any Number for calculating the prime factors: 350 2 5 7
 
Explanation:
 
In this example, we will be using a while loop only. Firstly, we have taken the input from the user as n. Secondly, we will set i value as 1. Thirdly, we will apply a while loop with checking condition as i should be less than or equal to n. Inside the loop, we will set the c value as 0 and apply the if and while the condition in it. At last, we will be checking if the value of c becomes equal to 2 then we print the value of i. hence, the prime factors are printed with the single-single value of them.
 
NOTE: Suppose we take input as 650 : the prime factors are 2,5,5,13 so, it will print 2,5,13 as all integers one time.
 
Conclusion
 
In this tutorial, we have seen how to find the prime factors of the number with 3 different methods. All the methods are explained in detail with the help of examples and their explanation. You can use any method which you like according to your need.
 
Источник