Hoi peter,

>WOW Walter, it's 4 times faster than the routine I sent! I wonder whether we can use this routine to find the next unknown prime number!

>>

>>CREATE CURSOR Prime (primenumber i)
>>INSERT INTO Prime VALUES (3)
>>
>>FOR I = 5 TO 100000 STEP 2
>>	nSQRT = SQRT(i)
>>	GO TOP
>>	LOCATE WHILE prime.primenumber =< nSQRT FOR I % prime.primenumber = 0
>>	IF !FOUND()
>>		INSERT INTO Prime VALUES ( i )
>>	ENDIF
>>ENDFOR
>>

Well this algoritm works well up to primes to 1,000,000 or so. After that the LOCATE line is getting a read hard time. IOW the program get slower and slower for each new Prime.

However you can workarround it by trowing in a new algoritm which takes another approach. It finds multiplications of primes and rules out these numbers for being a Prime. The holes it leaves are by definition primenumbers. On my machine, the following is faster when getting primes beyond 250000 or so.

CREATE CURSOR Prime (primenumber I, nextoccur B)
INSERT INTO Prime VALUES (3, 9)

INDEX ON NextOccur TAG occurance

t = seconds()

FOR nT = 5 TO 200000 STEP 2
	IF KEYMATCH(nT)
		DO WHILE SEEK(nT)
			nNext=NextOccur + 2*PrimeNumber
			DO WHILE KEYMATCH(nNext)
				nNext=nNext+2*PrimeNumber
			ENDDO
			REPLACE NextOccur WITH nNext
		ENDDO
	ELSE
		INSERT INTO Prime VALUES(nT,nT^2)
	ENDIF
ENDFOR

? seconds() - t

For finding the largest primenumber this approach is unsuitable because it takes to long to calculate all primenumbers up to a certain number. It takes a little more math. You can easely calculate a number that not even fits in a normal newspaper and is or contains a Primenumber larger than the largers primenumber used to calculate the number by multiplication of all known primenumber up to a certain point and add 1 to it:

for example:

(2 * 3 * 5 * 7 * 11) + 1 = 2311 (this is a primenumber)

This makes sense since 2310 can be divided by all primenumbers up to 11 and since for each number greater or equal to 2 (A x B) % A = 0 then ((A x B)+1) % A = 1 and is thus by definition not dividable by any of those primenumbers.

The hardtime ofcourse, is finding out of the calculated number is indeed a primenumber or can be divided by two or more primenumbers that are larger than the largest primenumbers used to calculating it.

Walter,