Alex Salmon wrote:
>
> my idea was that as all primes end in 1,3,7,9 (not all ending 1 3 7 9 are
> primes tho) so i wouldent need to start testing the number if it ended in
> say 5. sure this would slow down the working initily but as i get in to
> the say the 50000 or more it would dramticly reduce time in the long
> run.. i hope ;-)
Checking for divisible by 5 won't help much
Assume an algorith like
isprime (int X)
{
for i = 2 to squareroot(X) (2 and odd numbers only)
if X modulus i ==0 return false
return true;
}
Then numbers ending in 5 (10% of the smaple space) get picked up in 3
tests if not pre-filtered. Filtering for divisible by five adds an
extra step to all checks.
Adding a filter for even numbers helps a lot though, as it avoid the
system having to set the for loop up just to exit on the first
iteration.
On my system, checking the first million numbers :
No prefiltering: 11 seconds
Prefilter for Even: 6 seconds
Prefilter for ending in 5s as well: 6 seconds
My test code:
(spoiler space for anyone who wants to do it themselves)
/////////////////////////////////////////////////////////////////////
// Poor quality random number checker
// returns true if the test number is prime, false otherwise.
bool isprime (int testnum)
{
int i;
if ((testnum & 1) == 0) return false; //number is even
int nSqrt = (int)sqrt(testnum); //(do only once to avoid calling sqrt
every cycle of the for statement
// Test odd numbers from 3 to square root of testnum
for (i=3; i< nSqrt;i+=2)
{
if (testnum % i == 0) return false;
}
return true;
}
--
_____________________________________________________________
Network Operations Engineer - Big Pond Advance Satellite
Ericsson Australia - Level 5, 184 The Broadway, Sydney 2000
Ph: +61-416-085-390 Email: [EMAIL PROTECTED]
--
SLUG - Sydney Linux User Group Mailing List - http://slug.org.au/
More Info: http://slug.org.au/lists/listinfo/slug
