At 11:39 AM 11/17/98 -0200, Cyberknight wrote:
> I present here a program that checks if a number is or not
>prime. It is the fastest code I could think of. Half of it is a
>classical algorythm: divide X by 2; if no rest, it is not prime;
>divide X by 3; if no rest, it is not prime... and so on until
>X divided by X-1. I modified the algorythm in this way: if
>the number is not a multiple of 2, then it can be, at most,
>a multiple of 3, so one doesn't have to check till X-1, but
>(X-1)/2, or in other words, the multiples of the number can
>be at most (X-1)/2.
In fact, you only have to check until SQR(X).
Suppose X is not a prime.
Then you can find two numbers A and B, where A * B = X and A <= B.
If A > SQR(X) and B > SQR(X), then A * B > X. This is not the case, so A <=
SQR(X) or B <= SQR(X). Because A <= B, it is certain that A <= SQR(X).
This means that if X is not a prime, there is a number A <= SQR(X) which
devides X. So, you only have to check until SQR(X).
Modifications to the BASIC program:
25 DS=INT(SQR(DN))
30 IFDD<=DSTHENIF(DNMODDD)=0THENP=0:GOTO40ELSEDD=DD+2:GOTO30
Line 25 is there because SQR is a slow function. If you put SQR(DN) in the
IF statement, it is evaluated every loop, wasting a lot of time.
Bye,
Maarten
****
MSX Mailinglist. To unsubscribe, send an email to [EMAIL PROTECTED] and put
in the body (not subject) "unsubscribe msx [EMAIL PROTECTED]" (without the
quotes :-) Problems? contact [EMAIL PROTECTED] (www.stack.nl/~wiebe/mailinglist/)
****
