Friday, 14 July 2017

Is there a way to check if a number is prime with only a few details about the number?



I need to find a prime with the info, the sum of all its digits, the first and last digit and how much digits the number has.



For example, lets check if 13 is prime.




First digit: 1



Last digit: 3



Sum of all digits: 13 -> 1 + 3 = 4



Amount of digits: 2



How can I be sure that this number is 100% prime by only using this info?



Answer



Unfortunately no, you cannot deduce the primality of a number from the number and sum of its digits, in general. The best one can achieve, currently, is a polynomial time algorithm. There is more information on Wikipedia.



However, you can use the so-called divisibility criteria, to weed out composite numbers that have those factors for which you have a criterion.


No comments:

Post a Comment

real analysis - How to find limhrightarrow0fracsin(ha)h

How to find limh0sin(ha)h without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...