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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
Quickly gave me the following output (used all of 26.2 seconds to get there) :
And in case you are wondering what are the factors for 2009
And which is the next year which is a prime number ?
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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22