Hi,
Since I agree with the rest you wrote, I'll just quote this part:
CLAUDIO MASSAO KAWATA - 900293 wrote:
> A trivia about prime numbers: number 1 is not prime, as some
> people think. If it was, no other number would be, because they
> all would be multiples of at least one prime number (1 itself).
>
> 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. Line 20 checks if number is 2 or multiple
> of 2 (with that, you can step 2 by 2 instead of 1 by 1 of the
> classic algorythm). In line 30, "IF DD<=(DN/DD) THEN..." is my
> modification (the original should be "IF DD<DN THEN...").
> The program has to evaluate one extra division because of my
> modification, but it saves a lot with the reduction of the search
> range at each iteraction. Try it! Note: the program was originally
> written in C.
>
> 10 DEFINTA-Z:DD=3:P=1:INPUT"Number";DN:IFDN<2THENPRINTDN"is not a prime number
>(defined).":END
> 20 IFDN<>2THENIF(DNMOD2)=0THENP=0:DD=2:GOTO40
> 30 IFDD<=(DN/DD)THENIF(DNMODDD)=0THENP=0:GOTO40ELSEDD=DD+2:GOTO30
> 40 IFPTHENPRINTDN"is a prime number.":ENDELSEPRINTDN"is NOT a prime number (multiple
>of"DD")."
>
> ... Cyberknight...
> <Over>
If you want an even quicker algoritm, you don't need the division in the
loop, but you need a sqare root outside it (a bad approximation will do
fine). The point is, that when your program ends the loop, dd=dn/dd, or
in other words:dd^2=dn, or dd=sqr(dn). If you start with calculating
sqr(dn), it will therefor be faster. If this is not an integer, use the
first higher integer.
That will be, I think, the fastest way to check if one specific number
is prime. If, however, you want to calculate all prime numbers until a
certain one, there is a faster method: try dividing by all prime numbers
already found, until the number to check it with is higher than the
square root of dn. I don't have a program ready to show what I mean, but
I hope it is clear.
Bye,
shevek
****
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/)
****
