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 $lim_{hrightarrow 0}frac{sin(ha)}{h}$

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