# Tag Info

4

Primality testing is very fast with the Miller–Rabin algorithm [1]. You can use the deterministic variant with witnesses 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, and 37 to test any 64 bit number in $O(\log^3 n)$ time. This should take less than one second with any reasonable implementation. [1] https://en.wikipedia.org/wiki/Miller%E2%80%...

0

First of all, the question is phrased incorrectly. The following are equivalent and correct expressions of the intended question: why must we use a prime number as the modulo of the hash value (not "in the hashing function) or equivalently and more succinctly: why must the size of a hash table be a prime number? The proper answer to this question lies ...

2

Given any specific candidate divisor $d$, it is easy to check whether $d$ is a divisor of the number (the standard modular reduction algorithm is a generalization of those tricks you mentioned). This can be done for all $d$. However, it doesn't help with efficient factorization, because there are exponentially many candidate divisors, so trying each one, ...

Top 50 recent answers are included