-2

If a number n can be written as axb and m=sqrt(n). Here n=m*m. We say we only need to check upto m because min(a,b)<=m. So cant we take cube roots? Suppose we take n=21, then n=1x3x7. But Cube root is 2. Why does this method fail?

Abhishek Agrawal
  • 11
  • 3
  • Put this question on http://math.stackexchange.com. – Shreyash S Sarnayak Jan 08 '17 at 06:33
  • there are lots of duplicates: [Why do we check up to the square root of a prime number to determine if it is prime?](https://stackoverflow.com/q/5811151/995714), [Why we can use sqrt(n) instead of n/2 as an upper bound while finding prime numbers?](https://stackoverflow.com/q/21383349/995714) – phuclv Dec 22 '19 at 02:01
  • Does this answer your question? [Why do we check up to the square root of a prime number to determine if it is prime?](https://stackoverflow.com/questions/5811151/why-do-we-check-up-to-the-square-root-of-a-prime-number-to-determine-if-it-is-pr) – phuclv Dec 22 '19 at 02:01

1 Answers1

1

Consider n = 143 = 11 * 13. The cube root of 143 is between 5 and 6. If you only test divisibility by the primes up to 6, you will not find either of the two factors of n and will mistakenly conclude that 143 is prime.

user448810
  • 17,381
  • 4
  • 34
  • 59