How about big numbers? ( primality tests ) [closed]
-
27-04-2021 - |
Вопрос
Is this a 'real' task, that can be written on any language ( C/C++, for example )
So, my task is 'generate' random number with length over 50 digits ( maximum = 200 )?
Then, i must check this number on primality test.
So, is this task 'real' and how many time/resources it will consume?
alternative way is to generate prime Mersenn numbers or other numbers from special class ( which class could be used? )
Решение
There are efficient probabilistic algorithms for primality testing like Miller-Rabin that are usually used for such purposes.
Picking a random number and testing for primality using a randomized algorithm is efficient since the density of primes guarantees you that for n-bit numbers you need to pick around n numbers to test.
Другие советы
Use the Miller-Rabin primality test. Also, you'll need a library for big decimals, as numbers of 50 digits do not fit in a native datatype.
Here is a Javascript implementation of Miller-Rabin, which does 50 iterations of Miller-Rabin. It completes in a couple of seconds.