|
cp9876 wrote: The most important thing he should do is limit the testing to sqrt(N).
I believe this is not correct, assume you have an x composed from 2p where p is a prime, in this case it is clear that in certain circumstance sqrt(x) can be less than p (eg: 15838 = 7919 * 2, where 7919 > sqrt(15838)), for primal testing the sqrt(n) bound is ok, however its not suitable for the upper bound in this problem.
|
|
|
|
|
Arash Partow wrote: I believe this is not correct, assume you have an x composed from 2p where p is a prime, in this case it is clear that in certain circumstance sqrt(x) can be less than p (eg: 15838 = 7919 * 2, where 7919 > sqrt(15838)), for primal testing the sqrt(n) bound is ok, however its not suitable for the upper bound in this problem.
He's studying for the ACM competition - I don't want to spoon feed him! He can limit his testing to sqrt(N) but he has to modify his algorithm slightly for when InputCase is not 1 at the end.
In the example you give, he only needs to test until floor(sqrt(15838))=125, he will have only found 2 as a factor and InputCase will be 7919 after the 124 tests. He can then conclude the the remaining value in InputCase is the remaining prime factor. This is much more efficient than testing the remaining 15,703 factors.
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
|
|
|
|
|
cp9876 wrote: This is much more efficient than testing the remaining 15,703 factors.
true.
|
|
|
|
|
you're right, as long as one divides by the current number until the remainder is non-zero they will have taken out all of the multiple-of-factors as well, no need to explicitly only test/divide by primes.
good catch! 
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
