In my customary “Happy New Year” mail, I sent out a small note :
PS: Quiz : Is 2009 a prime number ? – Ans : No
Soon I started getting responses about that wisecrack of mine. The one that really stumped me came from a dear friend which said,
Enjoy the new year and happy computing. BTW is 200000000000000000000000000009 a prime number?
Soon enough found a piece of python code to find factors – Factor for Python which seemed to find all the factors for a number. Wasn’t likely to work too fast, so quickly modified it to the following code which finds all the prime factors for a number. Here’s the code
Update: The first version had a bug which did not show the largest factor. Has since been corrected.
"""
Get the factors for a number
(Note: Not optimised for tail recursion)
"""
def factor(n):
if n == 1: return [1]
i = 2
limit = n**0.5
while i <= limit:
if n % i == 0:
ret = factor(n/i)
ret.append(i)
return ret
i += 1
return [n]
if __name__ == "__main__":
import sys
for index in xrange(1,len(sys.argv)):
print "Factors for %s : %s" %(sys.argv[index], str(factor(int(sys.argv[index]))))
Quickly gave me the following output (used all of 26.2 seconds to get there) :
# python getfactors.py 200000000000000000000000000009 Factors for 200000000000000000000000000009 : [13430577524641L, 2094523, 89, 47, 47, 43, 29, 29]
And in case you are wondering what are the factors for 2009
# python getfactors.py 2009 Factors for 2009 : [41, 7, 7]
And which is the next year which is a prime number ?
# python getfactors.py 2011 Factors for 2011 : [2011]
Pretty playful hacking for 10 mins I thought.
Update: The code above was written in 10 mins, but it kept bothering me .. just wasn't idiomatic python. So once I got some time, I got back to it and decided to write a generator instead. The results obviously stay the same but the time came down from 26 seconds to 4.7 seconds. I of course threw in an additional optimisation which had nothing to do with a generator - basically the value of i no longer restarts from 2, it resumes with the last factor (the same that was yielded and moves on from there). Here's the new code implementing a generator.
"""
Generator for getting factors for a number
"""
def factor(n):
yield 1
i = 2
limit = n**0.5
while i <= limit:
if n % i == 0:
yield i
n = n / i
limit = n**0.5
else:
i += 1
if n > 1:
yield n
if __name__ == "__main__":
import sys
for index in xrange(1,len(sys.argv)):
print "Factors for %s : %s" %(sys.argv[index], [i for i in factor(int(sys.argv[index]))])
Related posts: (Automatically Generated)
why dont you keep the limit variable to like sqrt(n).That can be the highest factor other than itelsf
regards,
Varun
I could've .. just chose n**0.5 instead of sqrt(n). Thats already in the code.
How do you get Python to do more than 18 decimal places of accuracy in a division? When I try your algo I get the following factors:
[1037468051.0, 863693, 7, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 29]
sorry I just realized I am using Python 3.0, which changed the rule for division compared to old Python. Now, to get what you did, the division sign is // and not simply /
[i for i in factor(int(sys.argv[index]))]
should be just list([factor(int(sys.argv[index])))
You didn't see my prime factorization code, then? http://wj32.wordpress.com/2007/12/08/prime-fact...
Blame it on google .. it got me the other link first
and of course the fact that I wanted to get it done quickly. 
I just wrote this code (works in python 3.0 with the special “//” for division of integers). This code is much faster and will find your prime factors. I take advantage of the fact that 30=2*3*5, so any primes above 30 must be 1,7,11,13,17,23,or 29 modulo 30, otherwise the number would be divisible by 2,3 or 5. Here is the function:
def pfast(x):
remder = x
outcat=”1″
while 1:
if remder%2==0:
outcat=outcat+”*2″
remder=remder//2
else:
break
while 1:
if remder%3==0:
outcat=outcat+”*3″
remder=remder//3
else:
break
while 1:
if remder%5==0:
outcat=outcat+”*5″
remder=remder//5
else:
break
while 1:
if remder%7==0:
outcat=outcat+”*7″
remder=remder//7
else:
break
while 1:
if remder%11==0:
outcat=outcat+”*11″
remder=remder//11
else:
break
while 1:
if remder%13==0:
outcat=outcat+”*13″
remder=remder//13
else:
break
while 1:
if remder%17==0:
outcat=outcat+”*17″
remder=remder//17
else:
break
while 1:
if remder%19==0:
outcat=outcat+”*19″
remder=remder//19
else:
break
while 1:
if remder%23==0:
outcat=outcat+”*23″
remder=remder//23
else:
break
while 1:
if remder%29==0:
outcat=outcat+”*29″
remder=remder//29
else:
break
c=0
while 1:
top = remder**0.5+1
c=c+30
if c>top:
return outcat+”*”+str(remder)
while 1:
if remder%(c+1)==0:
outcat=outcat+”*”+str(c+1)
remder=remder//(c+1)
else:
break
while 1:
if remder%(c+7)==0:
outcat=outcat+”*”+str(c+7)
remder=remder//(c+7)
else:
break
while 1:
if remder%(c+11)==0:
outcat=outcat+”*”+str(c+11)
remder=remder//(c+11)
else:
break
while 1:
if remder%(c+13)==0:
outcat=outcat+”*”+str(c+13)
remder=remder//(c+13)
else:
break
while 1:
if remder%(c+17)==0:
outcat=outcat+”*”+str(c+17)
remder=remder//(c+17)
else:
break
while 1:
if remder%(c+23)==0:
outcat=outcat+”*”+str(c+23)
remder=remder//(c+23)
else:
break
while 1:
if remder%(c+29)==0:
outcat=outcat+”*”+str(c+29)
remder=remder//(c+29)
else:
break
There are supposed to be tab indentations. Not sure how to keep the tabs in a post
Yes, and I needed to know. What is the smallest prime factor?
I guessed around: 7
(Also, your “copy to clipboard” links don't work for me).
I hope you people realize how inefficient the code you've written is… After you've divided out all the 2's from the number, you still try to find out if it is divisible by 4,6,8,10,12… If nothing else, you should only do trial division by odd numbers. Or even better, if you can afford the memory cost, generate first a list of all prime numbers below sqrt(n), and then do trial division by those only…
Why does it output 1? The canonical way to write the prime factors of 4 is [2,2], not [1,2,2].
From Wikipedia, “Ω(n) for n = 1, 2, 3, … is 0, 1, 1, 2, …”
Ω(1) = 0 –> []
Ω(2) = 1 –> [2]
Ω(3) = 1 –> [3]
Ω(4) = 2 –> [2,2]
…
How aboout going with 6K + 1 where K is a Whole Number..
This gives all prime numbers with some numbers whose factors are prime numbers, like 25, 35, etc… So this is also not 100% correct, but can b helpful…
@Jaime Nice job. I’m surprised it took someone so long to mention this algorithm. When I wrote some code in C to do this, I was trying to generate all primes up to a certain number and I stored the primes I found just as you said. IIRC it took about 8 minutes to generate all primes under 10^7 on a P3 866Mhz.