We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Well a pretty simple/naive prime factorization algorithm works for the test cases. All you need to do is find the first factor (start testing with 2). The first number you find that works is guaranteed to be a prime number. Then keep dividing until the number is no longer divisible by that prime--keep the count (since you'll need that later). Then keep going until the number becomes 1.
Now I don't know whether or not you need the following "optimization", but I used it because I already had it from the Primitive Number problem. If the last number you end up with is a large prime, then you might needlessly test a bunch of numbers only to find out that there weren't any (i.e. it was prime). Use the fact that if two factors exist they will be on either side of the square root. So if the number you are currently testing, squares to something larger than the remaining number, then that number must be prime and you can quit and just add one instance of that large prime (rather than testing all of the numbers greater than the square root of that large prime--which will require substantially more testing than up to the square root).
Identify Smith Numbers
You are viewing a single comment's thread. Return to all comments →
Well a pretty simple/naive prime factorization algorithm works for the test cases. All you need to do is find the first factor (start testing with 2). The first number you find that works is guaranteed to be a prime number. Then keep dividing until the number is no longer divisible by that prime--keep the count (since you'll need that later). Then keep going until the number becomes 1.
Now I don't know whether or not you need the following "optimization", but I used it because I already had it from the Primitive Number problem. If the last number you end up with is a large prime, then you might needlessly test a bunch of numbers only to find out that there weren't any (i.e. it was prime). Use the fact that if two factors exist they will be on either side of the square root. So if the number you are currently testing, squares to something larger than the remaining number, then that number must be prime and you can quit and just add one instance of that large prime (rather than testing all of the numbers greater than the square root of that large prime--which will require substantially more testing than up to the square root).