AutoHotkey Community

After looking through the forum, and spending several minutes waiting for benchmarks to finish, I have concluded that this is the fastest prime number verifier (Finishing 1,000,000 iterations in which different integers were used in 3,588 MS on my computer) made in AutoHotkey.



It is based off Sieve of Eratosthenes, which is a mathematical algorithm used for generating prime numbers. If anyone has any ideas on how to make the function faster or knows of one that is faster, please do post.

_________________
Religion is false. >_>

The Sieve of Eratosthenes (O(N)) is better when you need all the primes up to a limit, the Sieve of Atkin (O(N/log log N) does the same thing but faster.
The Miller-Rabin primality test is a fast way to check if a number is likely not composite and it gets more accurate with more iterations.

I noticed while playing around with this it sometimes reports composite numbers as prime.

121, 143, 169, 181, 187

Here's an AHK solution from RosettaCode

I like my version...

Yours can be improved:

_________________
"Read the manual. Read it again. Search the forum.
Try something before asking. Show what you've tried."

Antonio França
My stuff: Google Profile

Not really: it finds numbers, which are not multiples of small primes. E.g. 121 = 11*11, but your IsPrime function finds it prime.

This function returns 1 for 9 or 15.

It can be simplified a bit, and sped up: it is enough to try potential divisors only up to Sqrt(a):However, my function (posted to RosettaCode) performs 15/4 = 3.75 times fewer iterations: you don't have to try even divisors (except 2), divisors of proper multiples of 3 or 5, etc. The actual speed relations depend on the AHK version and CPU type. Most likely the above simple loop is faster...

@Laszlo
Thanks for pointing that out. I tested it but probably didn't notice.
Code posted to RosettaCode is yours? Well, thank you, it's pretty fast.

_________________
"Read the manual. Read it again. Search the forum.
Try something before asking. Show what you've tried."

Antonio França
My stuff: Google Profile

Yes, someone posted my AHK function to RosettaCode. It is not meant to be fast (it uses slow recursive calls), but illustrative to sieving (by 2, 3 and 5) and reasonably short.

I've posted machine code prime testing functions to the forum, which are orders of magnitude faster than pure AHK scripts, and also scripts for the Miller-Rabin primality test, which is even faster for large input.

I'm guessing you are already aware of this, but this could be even faster by making sure "a" is of the form 6N+/-1 since that is the distribution of possible primes for all N. That doesn't change your function at all, but would matter if generating a list of all primes below a certain number.

You can use the two possible mod 6 candidates (33.3% of all integers), or the 8 possible mod 30 candidates (8/30 ~ 26.7% of all integers), and so on. For short numbers (up to 64 bits) cleverly generating the next divisor candidate is more costly than blindly trying the next odd number (50%), so the simple loop is faster in most cases. For long integers it is different, but there you should use something like the much faster Miller-Rabin tests.

Ahhh, so you are just as fascinated by primes as me. Good stuff.