[algorithm] How to create the most compact mapping n ? isprime(n) up to a limit N?

Way too late to the party, but hope this helps. This is relevant if you are looking for big primes:

To test large odd numbers you need to use the Fermat-test and/or Miller-Rabin test.

These tests use modular exponentiation which is quite expensive, for n bits exponentiation you need at least n big int multiplication and n big int divison. Which means the complexity of modular exponentiation is O(n³).

So before using the big guns, you need to do quite a few trial divisions. But don't do it naively, there is a way to do them fast. First multiply as many primes together as many fits into a the words you use for the big integers. If you use 32 bit words, multiply 3*5*7*11*13*17*19*23*29=3234846615 and compute the greatest common divisor with the number you test using the Euclidean algorithm. After the first step the number is reduced below the word size and continue the algorithm without performing complete big integer divisions. If the GCD != 1, that means one of the primes you multiplied together divides the number, so you have a proof it's not prime. Then continue with 31*37*41*43*47 = 95041567, and so on.

Once you tested several hundred (or thousand) primes this way, you can do 40 rounds of Miller-Rabin test to confirm the number is prime, after 40 rounds you can be certain the number is prime there is only 2^-80 chance it's not (it's more likely your hardware malfunctions...).

Examples related to algorithm

How can I tell if an algorithm is efficient? Find the smallest positive integer that does not occur in a given sequence Efficiently getting all divisors of a given number Peak signal detection in realtime timeseries data What is the optimal algorithm for the game 2048? How can I sort a std::map first by value, then by key? Finding square root without using sqrt function? Fastest way to flatten / un-flatten nested JSON objects Mergesort with Python Find common substring between two strings

Examples related to math

How to do perspective fixing? How to pad a string with leading zeros in Python 3 How can I use "e" (Euler's number) and power operation in python 2.7 numpy max vs amax vs maximum Efficiently getting all divisors of a given number Using atan2 to find angle between two vectors How to calculate percentage when old value is ZERO Finding square root without using sqrt function? Exponentiation in Python - should I prefer ** operator instead of math.pow and math.sqrt? How do I get the total number of unique pairs of a set in the database?

Examples related to data-structures

Program to find largest and second largest number in array golang why don't we have a set datastructure How to initialize a vector with fixed length in R C compiling - "undefined reference to"? List of all unique characters in a string? Binary Search Tree - Java Implementation How to clone object in C++ ? Or Is there another solution? How to check queue length in Python Difference between "Complete binary tree", "strict binary tree","full binary Tree"? Write code to convert given number into words (eg 1234 as input should output one thousand two hundred and thirty four)

Examples related to primes

Python Prime number checker Check if number is prime number Python Finding Prime Factors isPrime Function for Python Language How to find prime numbers between 0 - 100? Print series of prime numbers in python Calculating and printing the nth prime number Why do we check up to the square root of a prime number to determine if it is prime? Printing prime numbers from 1 through 100 Determining if a number is prime