Click here to Skip to main content
       

Algorithms

 
QuestionSpecify numbers as product of Primes? PinmemberIan Uy25-Jun-08 19:37 
AnswerRe: Specify numbers as product of Primes? Pinmembercp987625-Jun-08 21:32 
GeneralRe: Specify numbers as product of Primes? PinmemberIan Uy26-Jun-08 0:42 
AnswerRe: Specify numbers as product of Primes? PinmemberRobert.C.Cartaino26-Jun-08 4:48 
GeneralRe: Specify numbers as product of Primes? PinmemberIan Uy26-Jun-08 4:50 
GeneralRe: Specify numbers as product of Primes? PinmemberThe Developer8-Aug-08 7:03 
GeneralRe: Specify numbers as product of Primes? PinmemberIan Uy26-Jun-08 6:28 
GeneralRe: Specify numbers as product of Primes? PinmemberPaul Conrad28-Jun-08 5:44 
GeneralRe: Specify numbers as product of Primes? PinmemberIan Uy28-Jun-08 5:46 
GeneralRe: Specify numbers as product of Primes? PinmemberPaul Conrad28-Jun-08 6:11 
GeneralRe: Specify numbers as product of Primes? PinmemberRavi Bhavnani8-Aug-08 7:16 
GeneralRe: Specify numbers as product of Primes? Pinmembercp987628-Jun-08 20:27 
GeneralRe: Specify numbers as product of Primes? PinmvpLuc Pattyn29-Jun-08 2:42 
GeneralRe: Specify numbers as product of Primes? PinmemberMarkBrock27-Jun-08 18:46 
GeneralRe: Specify numbers as product of Primes? PinmemberPaul Conrad28-Jun-08 5:42 
GeneralRe: Specify numbers as product of Primes? PinmemberChandraRam2-Jul-08 22:49 
GeneralRe: Specify numbers as product of Primes? PinmemberMarkBrock2-Jul-08 23:06 
AnswerRe: Specify numbers as product of Primes? PinmemberMember 419459326-Jun-08 8:19 
GeneralRe: Specify numbers as product of Primes? PinmemberRobert.C.Cartaino26-Jun-08 8:47 
GeneralRe: Specify numbers as product of Primes? PinmemberIan Uy26-Jun-08 17:51 
GeneralRe: Specify numbers as product of Primes? Pinmembercp987629-Jun-08 14:57 
AnswerRe: Specify numbers as product of Primes? PinmemberArash Partow29-Jun-08 0:48 
GeneralRe: Specify numbers as product of Primes? [modified] Pinmembercp987629-Jun-08 3:53 
GeneralRe: Specify numbers as product of Primes? PinmvpLuc Pattyn29-Jun-08 4:40 
GeneralRe: Specify numbers as product of Primes? Pinmembercp987629-Jun-08 14:47 
GeneralRe: Specify numbers as product of Primes? PinmemberArash Partow30-Jun-08 2:54 
GeneralRe: Specify numbers as product of Primes? Pinmembercp987630-Jun-08 3:18 
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."

GeneralRe: Specify numbers as product of Primes? PinmemberArash Partow30-Jun-08 4:27 
GeneralRe: Specify numbers as product of Primes? PinmemberArash Partow30-Jun-08 2:17 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.


Advertise | Privacy | Mobile
Web03 | 2.8.140415.2 | Last Updated 6 Apr 2014
Copyright © CodeProject, 1999-2014
All Rights Reserved. Terms of Use
Layout: fixed | fluid