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