# What is the fastest algorithm to check if a number has only 3 divisors?

Which is the fastest way to check if a number has only 3 unique factors ? Any help will be highly appreciated?

-

check it's a square of another prime? – Patrick Li Oct 1 '12 at 16:12
@PatrickLi: another? – Marc van Leeuwen Oct 1 '12 at 16:41
@MarcvanLeeuwen check it's the square of a prime number. :) – Patrick Li Oct 1 '12 at 16:47

## 2 Answers

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$.

-

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.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 14, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.3, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.8821203708648682, "perplexity_flag": "head"}