Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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 2

up vote 1 down vote accepted

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

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.