Click here to Skip to main content
       

Algorithms

 
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 
Hi Luc,
 
True. The most important thing he should do is limit the testing to sqrt(N).
 
To factorise a number N, you need to test up to sqrt(N), and there are approximately
sqrt(N)/log(sqrt(N)) primes to test. For example, to factorise 1,000,000 you only need to test the 168 primes less than 1000, or 16.8% of the numbers less than 1000.
 
Using the simple algorithm you test 100% of the numbers less than sqrt(N):
if you eliminate the multiples of 2 you are down to testing about 50%
then eliminating the multiples of 3 drops you to testing 33.3%
then eliminating the multiples of 5 drops you to testing 26.7%
and so on.
 
the first few are probably worthwhile as you point out, but you then rapidly get in to diminishing returns, and may easily get to the stage where it is not worth the effort to save the time of the line
   if(InputCase%i==0)
 
I don't think multiple threads are worthwhile until you go past 32 bit arithmetic (even the simplest algorithm only has 2^16 tests to do).
 
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."
modified on Sunday, June 29, 2008 10:10 PM

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 
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 
Questionlogic of prob function in ms excel Pinmembersumit703425-Jun-08 0:40 
QuestionFactorials PinmemberIan Uy24-Jun-08 8:17 
AnswerRe: Factorials PinmemberTim Craig24-Jun-08 10:29 
GeneralRe: Factorials PinmemberIan Uy25-Jun-08 6:32 
GeneralRe: Factorials PinmemberTim Craig25-Jun-08 8:55 
GeneralRe: Factorials PinmvpLuc Pattyn25-Jun-08 11:01 
GeneralRe: Factorials PinmemberTim Craig25-Jun-08 21:06 
AnswerRe: Factorials Pinmembercp987624-Jun-08 12:33 
AnswerRe: Factorials PinmemberMatthew Butler24-Jun-08 12:38 
GeneralRe: Factorials Pinmembercp987624-Jun-08 14:05 
GeneralRe: Factorials PinmvpLuc Pattyn24-Jun-08 15:02 
GeneralRe: Factorials Pinmembercp987624-Jun-08 20:09 
GeneralRe: Factorials PinmvpLuc Pattyn24-Jun-08 23:53 
GeneralRe: Factorials Pinmembercp987625-Jun-08 2:27 
GeneralRe: Factorials PinmvpLuc Pattyn25-Jun-08 2:34 
GeneralRe: Factorials Pinmembercp987625-Jun-08 2:40 
AnswerRe: Factorials Pinmembertim_one14-Jul-08 8:37 
AnswerRe: Factorials PinmemberArash Partow25-Jun-08 2:14 
GeneralRe: Factorials PinmemberIan Uy25-Jun-08 6:26 
QuestionHow to determine the next x,y coordinate for a tank in a 2-D game... PinmemberEdmundisme18-Jun-08 8:35 
AnswerRe: How to determine the next x,y coordinate for a tank in a 2-D game... Pinmember73Zeppelin18-Jun-08 11:38 
GeneralRe: How to determine the next x,y coordinate for a tank in a 2-D game... PinmemberMatthew Butler18-Jun-08 11:44 
GeneralRe: How to determine the next x,y coordinate for a tank in a 2-D game... Pinmember73Zeppelin18-Jun-08 22:00 
GeneralRe: How to determine the next x,y coordinate for a tank in a 2-D game... PinmemberEdmundisme18-Jun-08 12:00 
AnswerRe: How to determine the next x,y coordinate for a tank in a 2-D game... PinmemberMatthew Butler18-Jun-08 11:41 
GeneralRe: How to determine the next x,y coordinate for a tank in a 2-D game... PinmemberEdmundisme18-Jun-08 12:01 
JokeRe: How to determine the next x,y coordinate for a tank in a 2-D game... PinmvpCPallini18-Jun-08 21:19 
QuestionPolyline offset algorithm Pinmemberbeko16-Jun-08 21:59 
AnswerRe: Polyline offset algorithm PinmemberAlan Balkany17-Jun-08 4:07 
GeneralRe: Polyline offset algorithm Pinmemberbeko17-Jun-08 4:43 
QuestionRe: Polyline offset algorithm Pinmvp CPallini17-Jun-08 7:03 
AnswerRe: Polyline offset algorithm Pinmemberbeko17-Jun-08 8:26 

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.140721.1 | Last Updated 1 Aug 2014
Copyright © CodeProject, 1999-2014
All Rights Reserved. Terms of Service
Layout: fixed | fluid