6
$\begingroup$

Why do we use only square root approach to find a number is prime or not? why not cube root & 4rth root?

$\endgroup$
3
  • 8
    $\begingroup$ If I understand you correctly, it's because when you check primality, you check if a number is a product of two numbers, not three or four. $\endgroup$
    – Git Gud
    Jun 29, 2015 at 12:00
  • $\begingroup$ possible duplicate of Is there a Non-prime Number that is Divisible only by Numbers Greater than its Square Root? $\endgroup$
    – Martin R
    Jun 29, 2015 at 19:19
  • $\begingroup$ @MartinR I don't think this is a duplicate; the cited question and its answers explain why it's sufficient to try numbers up to the square root, but not why it is not sufficient to just try numbers up to the cube root. It also seems to me (with respect to other votes for closing) that there is not really any missing context or details here; the question is naive but self-contained and it is an opportunity for people to try to enlighten someone's mathematical intuition. $\endgroup$
    – David K
    Jun 29, 2015 at 21:24

5 Answers 5

13
$\begingroup$

If $a\cdot b=N$ where $1<a\le b<N$

$N=ab\ge a^2\iff a^2\le N\implies a\le\sqrt N$

$\endgroup$
11
$\begingroup$

A more intuitive explanation of the same thing. For the same reasons.

The square root of 100 is 10. Let's say a x b = 100, for various pairs of a and b.

If a == b, then they are equal, and are the square root of 100, exactly. Which is 10.

If one of them is less than 10, the other has to be greater. For example, 5 x 20 == 100. One is greater than 10, the other is less than 10.

Thinking about a x b, if one of them goes down, the other must get bigger to compensate, so the product stays at 100. They pivot around the square root.

The square root of 101 is about 10.049875621. So if you're testing the number 101 for primality, you only need to try the integers up through 10, including 10. But 8, 9, and 10 are not themselves prime, so you only have to test up through 7, which is prime.

Because if there's a pair of factors with one of the numbers bigger than 10, the other of the pair has to be less than 10. If the smaller one doesn't exist, there is no matching larger factor of 101.

If you're testing 121, the square root is 11. You have to test the prime integers 1 through 11 (inclusive) to see if it goes in evenly. 11 goes in 11 times, so 121 is not prime. If you had stopped at 10, and not tested 11, you would have missed 11.

You have to test every prime integer greater than 2, but less than or equal to the square root, assuming you are only testing odd numbers.

$\endgroup$
3
  • 1
    $\begingroup$ A caveat about the last line, you only have to test prime numbers less than or equal to the square root. What method you use to find those primes is up to you. $\endgroup$
    – corsiKa
    Jun 29, 2015 at 19:23
  • $\begingroup$ corsiKa is of course, correct. That's what I think I must have meant at the time. $\endgroup$
    – RickyS
    Jul 3, 2015 at 4:17
  • $\begingroup$ Well, it's hard - if there was an easy way to test THOSE primes, you would just use that easy way to test your TARGET prime. So often times you just test for 2, and start at 3 going up by 2 every time. It's still really fast for small n. On my crappy desktop (6 years old), testing 9 digit number was basically instant. A large 18 digit prime number (9.81x10^17 or so) took 31 seconds, and I cut it in half with a single extra line of code. So it's still a decent method for any 64 bit number, usually. $\endgroup$
    – corsiKa
    Jul 3, 2015 at 5:08
4
$\begingroup$

If n is a sum of 2 addends, one addend must be $\leq n/2$
If n is a sum of 3 addends, one addend must be $\leq n/3$
If n is a sum of 4 addends, one addend must be $\leq n/4$
etc...

If n is a product of 2 factors, one factor must be $\leq \sqrt{n}$
If n is a product of 3 factors, one factor must be $\leq \sqrt[3]{n}$
If n is a product of 4 factors, one factor must be $\leq\sqrt[4]{n}$
etc...

Since having 2 factors is sufficient to be non-prime, $\sqrt{n}$ is used to bound the test.

$\endgroup$
3
$\begingroup$

Because it is true that every composite number $N$ has a prime factor at most equal to $\sqrt N$ but it is not true that every composite number has a prime factor at most equal to $\sqrt[k] N$ for $k\ge 3$. For instance, $N=p^2$, where $p$ is prime, has no prime factor at most equal to $\sqrt[k] N$ for any $k\ge 3$.

$\endgroup$
1
$\begingroup$

Consider the number $143$. This number is composite, not prime, because

$$11 \times 13 = 143.$$

But $$\sqrt[3]{143} \approx 5.229 < 11 < 13,$$ so if you test only possible factors up to $\sqrt[3]{143}$ then you will not check whether $11$ or $13$ divide $143$, and you will not discover that $143$ is not prime.

On the other hand, $$11 < \sqrt{143} \approx 11.958,$$ so if you test all possible prime factors less than $\sqrt{143}$ then you will (eventually) test whether $11$ divides $143$, and you will find out that $143$ is not prime. Moreover, as other answers have shown, this always works, even when you replace $143$ by some arbitrary positive integer $n$.

One counterexample is enough to show that an algorithm is incorrect. Sometimes one can refine an algorithm in the face of such a counterexample, for example here you might say you will apply the algorithm only to test primality of a number $n$ greater than $143$. But there are plenty of other, much larger, counterexamples—just take $n$ to be the product of any two primes that are "close" to each other—and no practical way to account for all the counterexamples (as there appear to be infinitely many of them). More precisely, I do not see any practical way that is easier than actually finding out (using a correct algorithm) whether the number $n$ is prime.

So the reason we use square root and not cube root is that the square root approach works and the cube root approach does not work. The fourth root approach also does not work, since $\sqrt[4]{n} < \sqrt[3]{n}$ for $n > 1$ and we already can see that $\sqrt[3]{n}$ is not always large enough.

$\endgroup$

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