Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Prime number test
#1
how do i test if a number is prime or not
#2
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
#3
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
#4
good idea. All prime numbers except 2 are not divisible by 2.
#5
What way we could calculate the fastest way possible using QM?

Perhaps using ASM...?

ex: http://www.findthatzipfile.com/search-6 ... me.zip.htm
#6
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
#7
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.
#8
Is possible integrate the fastest code in the Dll functions exported by QM?
#9
No. Maybe you can find an existing dll somewhere. Or good C/C++ source code, then I can compile it to dll.
#10
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?


Forum Jump:


Users browsing this thread: 1 Guest(s)