3 ms·
You only need to divide by prime numbers up to ceil(sqrt(your_number)). They don't know all prime numbers up to this number, but they can easily exclude many n
by ajuc 11y ago
You only need to divide by prime numbers up to ceil(sqrt(your_number)).
They don't know all prime numbers up to this number, but they can easily exclude many numbers (for example even).
- kale 11y agoThat would still take an eternity. They use special form primes (the big primes are all n+1 or n-1 forms, with n being easy to factor). If a Mersenne Number is prime, then the exponent must also be prime (74,207,281 is also prime). That cuts down on a lot of processing time. Also, all factors of a Mersenne Number, if it's composite, are of the form 2nk + 1, where the Mersenne number is written 2^n - 1. That also helps factor it. I generated a huge list of prime number indices and did some tests on them a couple of years ago. 25% of the Mersenne numbers have 2*n + 1 as a factor. That's even less computation time to find a large prime.
- skj 11y agoOr any composite number. If it's divisible by a composite number, it will also be divisible by the smaller primes.
- spdionis 11y agoThis are the simplest insights for optimizing primality test. A nice exercise to implement if you like algorithms. More info: https://en.m.wikipedia.org/wiki/Sieve_of_Eratosthenes https://en.m.wikipedia.org/wiki/Sieve_of_Eratosthenes