Hi Nadya

I have a suggestion about these coding puzzles. Keep them practical. I doubt anyone on the UT needs a prime number generator.

However I understood the original question was for a way to detect missing numbers in a sequence. That could be useful for accounting for missing invoices etc.


>>>>>I meant prime numbers, just didn't know the correct term. E.g. each number has only two dividors (1 and itself).
>>>>>
>>>>>1
>>>>>2
>>>>>3
>>>>>5
>>>>>7
>>>>>11
>>>>>13
>>>>>etc.
>>>>
>>>>It is convenient to have a UDF that returns .T. if the input is a prime number.
>>>>
>>>>An algorithm that is reasonable in terms of speed and simplicity, for numbers up to several millions, is:
>>>>
>>>>Divide input by 2
>>>>
>>>>Divide input by all odd numbers, from 3 to sqrt(input)
>>>>
>>>>Return .F. immediately if any of the divisions gives no remainder.
>>>>
>>>>You can then search for each prime number with a loop, also starting at 2, and then:
>>>>
>>>>

>>>>for i = 3 to MaxRange step 3
>>>>  if not seek(i) and IsPrime(i)
>>>>    insert into...
>>>>  endif
>>>>next
>>>>

>>>>
>>>>Hilmar.
>>>
>>>Hi Hilmar,
>>>
>>>I don't think, your method would be the most efficient. I was thinking about this problem a little bit, and here is a draft idea:
>>>
>>>Say, we have a table with N prime numbers in sequence (should not be any ommissions in this table). To define, if the number is prime or not, we can try to divide this number by each of the known prime numbers up till the squar root of the number. If this number would be prime, we would insert it into this Lookup Prime numbers table. However, I'm not yet convinced, that this one is the best algorithm...
>>
>>Nadia/Hilmar, try this piece of code. Inspired by Guido Diemer, my colleague, who himself was inspired by Erastostenes!
>>
>>

>>create cursor prime ( primenumber i )
>>insert into prime value ( 3 )
>>
>>MaxRange = 100000
>>
>>t = seconds()
>>for i = 5 to MaxRange step 2
>>  if IsPrime(i)
>>	insert into prime value ( i )
>>  endif
>>next
>>? seconds() - t
>>
>>func isprime
>>	lpar i
>>	local n
>>	scan
>>		n = prime.primenumber
>>		if int( i / n ) = i / n
>>			return .f.
>>		endif
>>		if n^2 > i
>>			exit
>>		endif
>>	endscan
>>	return .t.
>>

>
>Great!