Which is the fastest way to check if a number has only 3 unique factors ? Any help will be highly appreciated?
$\begingroup$
$\endgroup$
3
-
$\begingroup$ check it's a square of another prime? $\endgroup$– JACKY88Commented Oct 1, 2012 at 16:12
-
$\begingroup$ @PatrickLi: another? $\endgroup$– Marc van LeeuwenCommented Oct 1, 2012 at 16:41
-
$\begingroup$ @MarcvanLeeuwen check it's the square of a prime number. :) $\endgroup$– JACKY88Commented Oct 1, 2012 at 16:47
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
Supposing that by "only 3 divisors" you mean "exactly 3 divisors", the only such numbers are numbers of the form $p^2$, where $p$ is prime; they are divisible by $1, p, $ and $p^2$. So the first thing to try is to test if the number $n$ is a perfect square, which you can do efficiently by calculating the integer square root $i = \lfloor \sqrt n\rfloor$ and then checking to see if $i^2=n$. If not, $n$ fails. If so, $n$ has the desired property if and only if $i$ is prime, which you can check using any of the usual primality tests.
$\begingroup$
$\endgroup$
The fastest method will depend on the types of numbers you intend to check and how you are running the tests (pencil and paper, x86_64, etc.). But basically, check if the number has any small prime factors (say, the first 25: 2, 3, 5, ..., 97). If so, the number has exactly 3 divisors if and only if the number is the square of that prime. Otherwise you have a number with no tiny prime factors; now check if the number is a square. You can first test mod some promising moduli, like 63, 64, and 65. If it passes that test, take the integer square root $s$ and test if that, squared, gives the number. If not, the number has more than 3 divisors. If so, test if the remaining number is prime. The first step is using a probable-prime test, maybe checking if the number is a b-strong pseudoprime for some randomly-chosen $1 < b < s-1.$ If that fails the number is composite and so $s^2$ has more than three divisors. Otherwise apply a primality-proving test to $s$.
