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