Prime number test

[John]

how do i test if a number is prime or not

[Gintaras]

Simple but slow.
Function IsPrimeNumber

Code:

Copy      Help

;/
function! x

if(x<2) ret

int i si=sqrt(x)+1
for i 2 si
,if !(x%i)
,,;out "%i is divisible by %i" x i
,,ret

;out "%i is prime number" x
ret 1

[Lucas]

little faster.

Function IsPrimeNumber2

Code:

Copy      Help

;/
function! x

if(x<2) ret
if(x=2) ret 1
if(x%2=0) ret 0
int i si=sqrt(x)+1
for i 3 si 2
,if !(x%i)
,,;out "%i is divisible by %i" x i
,,ret

;out "%i is prime number" x
ret 1

[Gintaras]

good idea. All prime numbers except 2 are not divisible by 2.

[Lucas]

What way we could calculate the fastest way possible using QM?

Perhaps using ASM...?

ex: http://www.findthatzipfile.com/search-6 ... me.zip.htm

[Kevin]

Not sure about the fastest way but you can eliminate more numbers. based on The Sieve_of_Eratosthenes
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

[Gintaras]

I would simply create a dll, in C++ language.

In QM the fastest way is assembler, using __Tcc class. Or C, but TCC does not optimize it, therefore it is several times slower than asembler, although many times faster than QM.

[Lucas]

Is possible integrate the fastest code in the Dll functions exported by QM?

[Gintaras]

No. Maybe you can find an existing dll somewhere. Or good C/C++ source code, then I can compile it to dll.

[Lucas]

I found:

Function IsPrimeNumber3

Code:

Copy      Help

function int'n

if(n=1) ret 0
if(n<4) ret 1
if(n%2=0) ret 0
if(n<9) ret 1
if(n%3=0) ret 0
int r=sqrt(n)
int f=5
;bucle
if(f<=r)
,if((n%f)=0) ret 0
,if(n%(f+2)=0) ret 0
,f+6
,goto bucle
ret 1

Do you know why IsPrimeNumber3 is slower than IsPrimeNumber2?