[Date Prev][Date Next][Thread Prev][Thread Next] [Search] [Date Index] [Thread Index]

Re: [MacPerl] Prime Numbers



On Mon, 16 Aug 1999 11:53:57 -0500 (CDT), Matthew Langford wrote:

>What is an obvious (brute force) way of testing for primes?  Isn't it to
>try dividing by all the numbers less than it?

>That is what this algorithm does, only it is using the pattern matching
>engine to do all the work.

So a different algorithm should be able to give a large speed boost. For
example (also crude, but a lot faster):

 - Try to divide by all primes found so far (except 1).

 - You never need go beyond sqrt(number). If it has a factor larger than
sqrt(number), it must have a factor below it too.

 - Apart from 2, you needn't test any even numbers.

	Bart.

===== Want to unsubscribe from this list?
===== Send mail with body "unsubscribe" to macperl-request@macperl.org