# Prime in Numbers with Wheel Factorization

Sep 14th, 2021
1,050
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1.
2. Given a positive number n > 1 find the prime factor decomposition of n. The result will be a string with the following form :
3.
4. "(p1**n1)(p2**n2)...(pk**nk)"
5. with the p(i) in increasing order and n(i) empty if n(i) is 1.
6. @EXAMPLE:
7. n = 86240 should return "(2**5)(5)(7**2)(11)"
8. n= 782611830 should return "(2)(3**2)(5)(7**2)(11)(13)(17)(73)"
9.
10.
11. -------------------------------------------------------------------------------------------------------------------------------------
12.
13.
14.
15. import math
16.
17. def prime_factors(n):
18.     result=''
19.     count = 0
20.     while n%2==0:
21.         n/=2
22.         count+=1
23.     if count==1:
24.         x2=("("+"2"+")")
25.         for cnt01 in x2:
26.             result+=cnt01
27.     elif count:
28.         x= ("(" + "2**" + str(count) + ")" )
29.         for cnt02 in x:
30.             result+=cnt02
31.
32.
33.     for k in range(3,int(math.sqrt(n)+1),2):
34.         count=0
35.         while n%k==0 and n!=1:
36.             n/=k
37.             count+=1
38.         if count==1:
39.             z=("("+str(k)+")")
40.             for cnt in z:
41.                 result+=cnt
42.
43.         elif count:
44.             y= ("("+str(k) + "**" + str(count)+")")
45.             for cnt1 in y:
46.                 result+=cnt1
47.     if n > 2:
48.         x1=("("+str(int(n))+")")
49.         for cnt2 in x1:
50.             result+=cnt2
51.
52.     return result
RAW Paste Data