Hi,
[prime]
>> 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.":END
>> ELSEPRINTDN"is NOT a prime number (multiple of"DD")."
>If you want an even quicker algoritm, you don't need the division in the
>loop, but you need a sqare root outside it [snip]
There is another method which could be faster for really large numbers.
The point is, that with the algorithm above, you still check a lot of
possible divisors that don't need to be checked, namely all non-prime
odd numbers. (9, 15, 19, 21 etc).
The trick is to define an array P[SRQ(DN)], which is initially filled
with "1"s. Now, do the next:
100 FOR I=1 TO SQR(DN) ' I know - SQR(DN) can be precalculated
110 IF P[I]=0 THEN 140
120 J = 2*I
130 IF J < SQR(DN) THEN P[J] = 0: J=J+I: GOTO 130
140 NEXT I
Then, only those elements of P[] whose indexes are prime will still
contain "1", the rest will be "0". Now, you only need to check these
as possible divisors for DN. For small DN, the effort of creating
the prime array is much higher than simply checking all odd numbers,
that's why it can only work for large DN. Actually I'm not even sure
if there _is_ a point beyond which this method is faster than the
one mentioned first. Ah well, it's fun to see it anyway, ain't it :-)
150 FOR I=2 TO SQR(DN)
160 IF P[I] = 0 THEN 180
170 IF (DN MOD I) = 0 THEN PRINT DN "is not prime. multiple of " I: END
180 NEXT I
190 PRINT DN "is prime"
Further optimizations left as excercise for the reader :-)
By the way, he above method of calculating primes is known as the
"sieve of Erathostenes".
Eric (primes are an odd bunch o' numbers)
****
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/)
****
