Quote:
Originally Posted by CRGreathouse
Of course for nonMersenne numbers there still algorithms much faster than trial division. Below 2^64 BPSW works, above that a prp test and ECPP is good (and you can do less if you only need nearcertainty, like 99.999999%).

Yes, I was about to say that. My script is for
any prime. An algorithm that works 100.0% of the time and is fast? I have done many trials and tests with different methods and this modular trial division is the only method that always returns 100% correct. Sieves such as the Sieve of Eratosthenes are fast, but can take a while to initialize sieve data into memory. Sieves can also be ram expensive and only work up to a certain number before you reach your memory limit. Read the description of my code. If the program is taking too long, then terminate the process. If you enter a huge number that is 300 thousand digits long, if it is not prime, the program will be able to realize it in under a few seconds 99% of the time. If it runs....and keeps running, it has a much higher chance of primeness especially if you have a system with a high corecount because it takes evenly spaced samples of the whole number at once. This gives it a higher chance to find an odd divisor by sampling calculations of the number from multiple vantage points simultaneously. The script also accepts pythonic syntax such as 2^611 as 2**611 for a Mersenne Prime around 2.3 quintillion. On my 8 core 16 thread i9 it does this in around 20 seconds at 4.7 ghz.