12,825,743 members (37,563 online)

# Algorithms

 Re: Specify numbers as product of Primes? Member 419459326-Jun-08 9:19 Member 4194593 26-Jun-08 9:19
 Re: Specify numbers as product of Primes? Robert.C.Cartaino26-Jun-08 9:47 Robert.C.Cartaino 26-Jun-08 9:47
 Re: Specify numbers as product of Primes? Ian Uy26-Jun-08 18:51 Ian Uy 26-Jun-08 18:51
 Re: Specify numbers as product of Primes? cp987629-Jun-08 15:57 cp9876 29-Jun-08 15:57
 Re: Specify numbers as product of Primes? Arash Partow29-Jun-08 1:48 Arash Partow 29-Jun-08 1:48
 Re: Specify numbers as product of Primes? [modified] cp987629-Jun-08 4:53 cp9876 29-Jun-08 4:53
 Re: Specify numbers as product of Primes? Luc Pattyn29-Jun-08 5:40 Luc Pattyn 29-Jun-08 5:40
 Re: Specify numbers as product of Primes? cp987629-Jun-08 15:47 cp9876 29-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
 Re: Specify numbers as product of Primes? Arash Partow30-Jun-08 3:54 Arash Partow 30-Jun-08 3:54
 Re: Specify numbers as product of Primes? cp987630-Jun-08 4:18 cp9876 30-Jun-08 4:18
 Re: Specify numbers as product of Primes? Arash Partow30-Jun-08 5:27 Arash Partow 30-Jun-08 5:27
 Re: Specify numbers as product of Primes? Arash Partow30-Jun-08 3:17 Arash Partow 30-Jun-08 3:17
 logic of prob function in ms excel sumit703425-Jun-08 1:40 sumit7034 25-Jun-08 1:40
 Factorials Ian Uy24-Jun-08 9:17 Ian Uy 24-Jun-08 9:17
 Re: Factorials Tim Craig24-Jun-08 11:29 Tim Craig 24-Jun-08 11:29
 Re: Factorials Ian Uy25-Jun-08 7:32 Ian Uy 25-Jun-08 7:32
 Re: Factorials Tim Craig25-Jun-08 9:55 Tim Craig 25-Jun-08 9:55
 Re: Factorials Luc Pattyn25-Jun-08 12:01 Luc Pattyn 25-Jun-08 12:01
 Re: Factorials Tim Craig25-Jun-08 22:06 Tim Craig 25-Jun-08 22:06
 Re: Factorials cp987624-Jun-08 13:33 cp9876 24-Jun-08 13:33
 Re: Factorials Matthew Butler24-Jun-08 13:38 Matthew Butler 24-Jun-08 13:38
 Re: Factorials cp987624-Jun-08 15:05 cp9876 24-Jun-08 15:05
 Re: Factorials Luc Pattyn24-Jun-08 16:02 Luc Pattyn 24-Jun-08 16:02
 Re: Factorials cp987624-Jun-08 21:09 cp9876 24-Jun-08 21:09
 Re: Factorials Luc Pattyn25-Jun-08 0:53 Luc Pattyn 25-Jun-08 0:53
 Last Visit: 31-Dec-99 19:00     Last Update: 28-Mar-17 6:16 Refresh « Prev1...161162163164165166167168169170 Next »

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

Web01 | 2.8.170308.1 | Last Updated 22 Mar 2017