Click here to Skip to main content
12,240,874 members (78,087 online)

Algorithms

 
GeneralRe: Specify numbers as product of Primes? Pin
cp987628-Jun-08 21:27
membercp987628-Jun-08 21:27 
GeneralRe: Specify numbers as product of Primes? Pin
Luc Pattyn29-Jun-08 3:42
mvpLuc Pattyn29-Jun-08 3:42 
GeneralRe: Specify numbers as product of Primes? Pin
MarkBrock27-Jun-08 19:46
memberMarkBrock27-Jun-08 19:46 
GeneralRe: Specify numbers as product of Primes? Pin
Paul Conrad28-Jun-08 6:42
memberPaul Conrad28-Jun-08 6:42 
GeneralRe: Specify numbers as product of Primes? Pin
ChandraRam2-Jul-08 23:49
memberChandraRam2-Jul-08 23:49 
GeneralRe: Specify numbers as product of Primes? Pin
MarkBrock3-Jul-08 0:06
memberMarkBrock3-Jul-08 0:06 
AnswerRe: Specify numbers as product of Primes? Pin
Member 419459326-Jun-08 9:19
memberMember 419459326-Jun-08 9:19 
GeneralRe: Specify numbers as product of Primes? Pin
Robert.C.Cartaino26-Jun-08 9:47
memberRobert.C.Cartaino26-Jun-08 9:47 
GeneralRe: Specify numbers as product of Primes? Pin
Ian Uy26-Jun-08 18:51
memberIan Uy26-Jun-08 18:51 
GeneralRe: Specify numbers as product of Primes? Pin
cp987629-Jun-08 15:57
membercp987629-Jun-08 15:57 
AnswerRe: Specify numbers as product of Primes? Pin
Arash Partow29-Jun-08 1:48
memberArash Partow29-Jun-08 1:48 
GeneralRe: Specify numbers as product of Primes? [modified] Pin
cp987629-Jun-08 4:53
membercp987629-Jun-08 4:53 
GeneralRe: Specify numbers as product of Primes? Pin
Luc Pattyn29-Jun-08 5:40
mvpLuc Pattyn29-Jun-08 5:40 
GeneralRe: Specify numbers as product of Primes? Pin
cp987629-Jun-08 15:47
membercp987629-Jun-08 15: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? Pin
Arash Partow30-Jun-08 3:54
memberArash Partow30-Jun-08 3:54 
GeneralRe: Specify numbers as product of Primes? Pin
cp987630-Jun-08 4:18
membercp987630-Jun-08 4:18 
GeneralRe: Specify numbers as product of Primes? Pin
Arash Partow30-Jun-08 5:27
memberArash Partow30-Jun-08 5:27 
GeneralRe: Specify numbers as product of Primes? Pin
Arash Partow30-Jun-08 3:17
memberArash Partow30-Jun-08 3:17 
Questionlogic of prob function in ms excel Pin
sumit703425-Jun-08 1:40
membersumit703425-Jun-08 1:40 
QuestionFactorials Pin
Ian Uy24-Jun-08 9:17
memberIan Uy24-Jun-08 9:17 
AnswerRe: Factorials Pin
Tim Craig24-Jun-08 11:29
memberTim Craig24-Jun-08 11:29 
GeneralRe: Factorials Pin
Ian Uy25-Jun-08 7:32
memberIan Uy25-Jun-08 7:32 
GeneralRe: Factorials Pin
Tim Craig25-Jun-08 9:55
memberTim Craig25-Jun-08 9:55 
GeneralRe: Factorials Pin
Luc Pattyn25-Jun-08 12:01
mvpLuc Pattyn25-Jun-08 12:01 
GeneralRe: Factorials Pin
Tim Craig25-Jun-08 22:06
memberTim Craig25-Jun-08 22:06 
AnswerRe: Factorials Pin
cp987624-Jun-08 13:33
membercp987624-Jun-08 13:33 
AnswerRe: Factorials Pin
Matthew Butler24-Jun-08 13:38
memberMatthew Butler24-Jun-08 13:38 
GeneralRe: Factorials Pin
cp987624-Jun-08 15:05
membercp987624-Jun-08 15:05 
GeneralRe: Factorials Pin
Luc Pattyn24-Jun-08 16:02
mvpLuc Pattyn24-Jun-08 16:02 
GeneralRe: Factorials Pin
cp987624-Jun-08 21:09
membercp987624-Jun-08 21:09 
GeneralRe: Factorials Pin
Luc Pattyn25-Jun-08 0:53
mvpLuc Pattyn25-Jun-08 0:53 
GeneralRe: Factorials Pin
cp987625-Jun-08 3:27
membercp987625-Jun-08 3:27 
GeneralRe: Factorials Pin
Luc Pattyn25-Jun-08 3:34
mvpLuc Pattyn25-Jun-08 3:34 
GeneralRe: Factorials Pin
cp987625-Jun-08 3:40
membercp987625-Jun-08 3:40 
AnswerRe: Factorials Pin
tim_one14-Jul-08 9:37
membertim_one14-Jul-08 9:37 
AnswerRe: Factorials PinPopular
Arash Partow25-Jun-08 3:14
memberArash Partow25-Jun-08 3:14 
GeneralRe: Factorials Pin
Ian Uy25-Jun-08 7:26
memberIan Uy25-Jun-08 7:26 
QuestionHow to determine the next x,y coordinate for a tank in a 2-D game... Pin
Edmundisme18-Jun-08 9:35
memberEdmundisme18-Jun-08 9:35 
AnswerRe: How to determine the next x,y coordinate for a tank in a 2-D game... Pin
73Zeppelin18-Jun-08 12:38
member73Zeppelin18-Jun-08 12:38 
GeneralRe: How to determine the next x,y coordinate for a tank in a 2-D game... Pin
Matthew Butler18-Jun-08 12:44
memberMatthew Butler18-Jun-08 12:44 
GeneralRe: How to determine the next x,y coordinate for a tank in a 2-D game... Pin
73Zeppelin18-Jun-08 23:00
member73Zeppelin18-Jun-08 23:00 
GeneralRe: How to determine the next x,y coordinate for a tank in a 2-D game... Pin
Edmundisme18-Jun-08 13:00
memberEdmundisme18-Jun-08 13:00 
AnswerRe: How to determine the next x,y coordinate for a tank in a 2-D game... Pin
Matthew Butler18-Jun-08 12:41
memberMatthew Butler18-Jun-08 12:41 
GeneralRe: How to determine the next x,y coordinate for a tank in a 2-D game... Pin
Edmundisme18-Jun-08 13:01
memberEdmundisme18-Jun-08 13:01 
JokeRe: How to determine the next x,y coordinate for a tank in a 2-D game... Pin
CPallini18-Jun-08 22:19
mvpCPallini18-Jun-08 22:19 
QuestionPolyline offset algorithm Pin
beko16-Jun-08 22:59
memberbeko16-Jun-08 22:59 
AnswerRe: Polyline offset algorithm Pin
Alan Balkany17-Jun-08 5:07
memberAlan Balkany17-Jun-08 5:07 
GeneralRe: Polyline offset algorithm Pin
beko17-Jun-08 5:43
memberbeko17-Jun-08 5:43 
QuestionRe: Polyline offset algorithm Pin
CPallini17-Jun-08 8:03
mvp CPallini17-Jun-08 8:03 
AnswerRe: Polyline offset algorithm Pin
beko17-Jun-08 9:26
memberbeko17-Jun-08 9:26 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    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
Web02 | 2.8.160426.1 | Last Updated 18 Apr 2016
Copyright © CodeProject, 1999-2016
All Rights Reserved. Terms of Service
Layout: fixed | fluid