Optimal Primes1292 words. Time to Read: About 12 minutes.
If you like math, and you’re learning how to program, I see absolutely no reason why you should not know about Project Euler. “Project Yooler?!” you ask incredulously. “What outlandish nonsense is this?” You’re in for a treat. It’s an archive of puzzles that are math-based and generally not solvable by hand. There’s not a whole lot to it. It asks a question like ‘what is the 10001st prime number?’ and you can submit your answer. Once you get the answer correct, you get access to the question’s forum, where you can discuss answers and see other people’s solutions.
The reason I bring this up is because I was working on a few of the problems today and I had what I thought were some reasonably efficient solutions that used some not-your-every-day tricks. I’ll just show you what I mean. WARNING: SPOILER ALERT! Here’s the first question:
The prime factors of 13195 are 5, 7, 13, and 29. What is the largest prime factor of 600851475143?
Let’s talk about some options. First, it’s always best to think about the simplest, most naive solution. We could list every number from 1 to 600851475143 and check if that number is both prime and a factor in our number. Of course, that would require us to figure out if each number is prime, and that could require (again, in the most naive solution) looping from 2 through to whatever the current number was to see if any number in between divided evenly. If not, then it’s prime and we win. This sounds like it could be at least O(n^2) in complexity.
For those that aren’t familiar with Big-O notation, that’s a topic for another time, but right now the important thing is that if we double the size of the number we’re getting the largest prime factor of, the calculation time goes up by roughly 4x. Triple is 9x, etc. Not going to work for us.
Here’s my solution:
If you thought that was cool, hold on to your knickers! The next one builds on these concepts.
2520 is the smallest number that can be divided by all numbers between 1 and 10 (inclusive). What is the smallest positive integer that can be evenly divided by all numbers between 1 and 20 (also inclusive)?
OK. What are your first thoughts? Here are mine. My first snap intuition is to just multiply all of the numbers together. Ah, but 10 already works if a number is divisible by 2 and 5. We’ve got some repeating that is driving our final product up. I guess we need to see how many prime factors are really required. One other thought worth mentioning is again the naive solution. Start at 21 and continue searching upward (
if i % 2 == 0, if i % 3 == 0, if i % 4 == 0) until we find the answer. I’m going to see if I can do better though, because there’s no upper limit guarantee on that and I hate to leave a while loop to just run wild. Here’s my solution, which I will then explain.
Anyways, I thought these were some neat solutions. I mean, come on! Recursive delegating generators! The drama! The flair! Anyways, if you can come up with a better way to do it, let me know at firstname.lastname@example.org. See you next time!Author: Ryan Palo | Tags: algorithms python puzzle | Buy me a coffee