Why do we check up to the square root of a number to determine if the number is prime?

Question

To test whether a number is prime or not, why do we have to test whether it is divisible only up to the square root of that number?

Contain

because if n = a*b and a <= b then a*a <= a*b = n. – Stopwatch

To clarify, this means we have to test only till floor(sqrt(n)). – Intone

mathandmultimedia.com/2012/06/02/… – Hilaryhilbert

Answer 1

If a number n is not a prime, it can be factored into two factors a and b:

n = a * b

Now a and b can't be both greater than the square root of n, since then the product a * b would be greater than sqrt(n) * sqrt(n) = n. So in any factorization of n, at least one of the factors must be less than or equal to the square root of n, and if we can't find any factors less than or equal to the square root, n must be a prime.

Alveolus

How does sqrt(n) have to be precise enough for this property to hold given that we are using floating points. – Arezzini

@Benoît You can always use the check i * i <= n instead of i <= sqrt(n) if you want to avoid the intricacies of floating-point numbers. – Alveolus

Since it doesn't hurt (except for sometimes an additional division) to check one more divisor, you can just calculate ceil(sqrt(n)). – Ripleigh

@Ripleigh In some cases this might be useful, but this all heavily depends on implementation details (programming language, hardware, data types, libraries), none of which are known in this general consideration. – Alveolus

useful or not, what @Ripleigh had proposed is never hurtful, and costs almost nothing. better safe than sorry. – Stopwatch

@WillNess Even ceil(sqrt(n)) may not be enough depending on environment, e.g. when the floating-point type doesn't have enough precision to represent sqrt(n) even if it's an integer (which in practice would probably mean that you can't check all numbers up to sqrt(n) anyway). I just feel there are too many unknowns here. The approach of checking i * i <= n should always work, though. – Alveolus

except for the overflow. :) i <= n / i probably doesn't have this problem. – Stopwatch

It's not true that at least one of the factors must be smaller than the square root of n. Consider, for instance, 4 = 2 * 2. In this case, the two factors are equal to the square root of n. I suppose they should not be larger than the square root of n. – Woodworker

@HiltonFernandes The answer stated that in the very next sentence. I changed the wording in the first sentence to match the next sentence now, though I the old version might have been more readable. – Alveolus

Sorry for being picky, @SvenMarnach The art of commenting and explaining a mathematical proof seems to be almost as difficult as the art of creating the proof itself. – Woodworker

Of all answers to that question, yours was the most clear and comprehensible. I was starting to think I was too thick to get it. Thank you – Pharmacopsychosis

Answer 2

Let's say m = sqrt(n) then m × m = n. Now if n is not a prime then n can be written as n = a × b, so m × m = a × b. Notice that m is a real number whereas n, a and b are natural numbers.

Now there can be 3 cases:

1. a > m ⇒ b < m
2. a = m ⇒ b = m
3. a < m ⇒ b > m

In all 3 cases, min(a, b) ≤ m. Hence if we search till m, we are bound to find at least one factor of n, which is enough to show that n is not prime.

Tribadism

n = 12 m = sqrt(12) = 3.46, a = 2, b = 6. n = mm i.e. 12=3.46*3.46 and n = ab i.e 12=2*6. Now condition 3. a < m < b i.e 2 < 3.46 < 6. So to check prime we only need to check for number less than 3.46 which is 2 to find out that number is not prime. Hence, check divisibility by numbers less than or equal to(if n = 4, m=a=b=2) square root of n. – Stipend

I think we should highlight the assumption first. Assume n is not a prime, and the prove it, otherwise it's a prime. – Glassman

Actually, I'm not convinced it is a better answer. It is a correct answer, but it doesn't really answer the question. It just describes some other dynamics around primes and the sqrt. @Sven's answers is both succinct, and doesn't create more questions in the process. – Binominal

I rolled back to the last good version. you missed it when someone needlessly removed a word ('hence'), which is needed for the flow. – Stopwatch

I like this answer better than the accepted answer - the accepted answer does not explain well why a and b both cannot be greater than sqrt(n). 3 cases made it clear to me. – Terse

Answer 3

Because if a factor is greater than the square root of n, the other factor that would multiply with it to equal n is necessarily less than the square root of n.

Rodomontade

Answer 4

Suppose n is not a prime number (greater than 1). So there are numbers a and b such that

n = ab      (1 < a <= b < n)

By multiplying the relation a<=b by a and b we get:

a^2 <= ab
 ab <= b^2

Therefore: (note that n=ab)

a^2 <= n <= b^2

Hence: (Note that a and b are positive)

a <= sqrt(n) <= b

So if a number (greater than 1) is not prime and we test divisibility up to square root of the number, we will find one of the factors.

Kathernkatheryn

Answer 5

It's all really just basic uses of Factorization and Square Roots.

It may appear to be abstract, but in reality it simply lies with the fact that a non-prime-number's maximum possible factorial would have to be its square root because:

sqrroot(n) * sqrroot(n) = n.

Given that, if any whole number above 1 and below or up to sqrroot(n) divides evenly into n, then n cannot be a prime number.

Pseudo-code example:

i = 2;

is_prime = true;

while loop (i <= sqrroot(n))
{
  if (n % i == 0)
  {
    is_prime = false;
    exit while;
  }
  ++i;
}

Allowance

Brilliant observation. Using this observation to create a guard statement in Swift in conjunction with this handy https://mcmap.net/q/74512/-check-if-number-is-decimal-with-swift-closed to do an early exit from a calculation rather than wasting computational power. Thank you for posting. – Acidfast

@Acidfast I must confess that after coming back to this answer, I did find an error at the time of your posting. You cannot perform division on a 0, and in theory if you could ++i would become the number 1, which would always return false (because 1 divides into everything). I've corrected the answer above. – Allowance

Yep...I addressed that in my code...your square root observation is a great way to throw out a non-prime value early before you begin running calculations. I was getting killed on a big number that turned out to be a big waste of time. I also learned this algorithm can substantially reduce processing times on big numbers, too. en.wikipedia.org/wiki/Miller–Rabin_primality_test – Acidfast

You can optimize the ( pseudo) code by checking if the sqrroot(n) is a whole number or not. If it is, then n is not a prime. If not, then the checking inside the while loop should happen ( by taking floor of sqrroot(n)). – Morrissey

Answer 6

Let's suppose that the given integer N is not prime,

Then N can be factorized into two factors a and b , 2 <= a, b < N such that N = a*b. Clearly, both of them can't be greater than sqrt(N) simultaneously.

Let us assume without loss of generality that a is smaller.

Now, if you could not find any divisor of N belonging in the range [2, sqrt(N)], what does that mean?

This means that N does not have any divisor in [2, a] as a <= sqrt(N).

Therefore, a = 1 and b = n and hence By definition, N is prime.

...

Further reading if you are not satisfied:

Many different combinations of (a, b) may be possible. Let's say they are:

(a₁, b₁), (a₂, b₂), (a₃, b₃), ..... , (a_k, b_k). Without loss of generality, assume a_i < b_i, 1<= i <=k.

Now, to be able to show that N is not prime it is sufficient to show that none of a_i can be factorized further. And we also know that a_i <= sqrt(N) and thus you need to check till sqrt(N) which will cover all a_i. And hence you will be able to conclude whether or not N is prime.

...

Langobard

Answer 7

So to check whether a number N is Prime or not. We need to only check if N is divisible by numbers<=SQROOT(N). This is because, if we factor N into any 2 factors say X and Y, ie. N=XY. Each of X and Y cannot be less than SQROOT(N) because then, XY < N Each of X and Y cannot be greater than SQROOT(N) because then, X*Y > N

Therefore one factor must be less than or equal to SQROOT(N) ( while the other factor is greater than or equal to SQROOT(N) ). So to check if N is Prime we need only check those numbers <= SQROOT(N).

Lief

Answer 8

Let's say we have a number "a", which is not prime [not prime/composite number means - a number which can be divided evenly by numbers other than 1 or itself. For example, 6 can be divided evenly by 2, or by 3, as well as by 1 or 6].

6 = 1 × 6 or 6 = 2 × 3

So now if "a" is not prime then it can be divided by two other numbers and let's say those numbers are "b" and "c". Which means

a=b*c.

Now if "b" or "c" , any of them is greater than square root of "a "than multiplication of "b" & "c" will be greater than "a".

So, "b" or "c" is always <= square root of "a" to prove the equation "a=b*c".

Because of the above reason, when we test if a number is prime or not, we only check until square root of that number.

Misogamy

b & c <= Math.sqrt(n)?; It should be rather b || c ( b or c) since if n=6, b=3, c=2 then Math.sqrt(n) > c. – Selfliquidating

Thanks buddy for the correction. doing the correction. :) – Misogamy

Answer 9

Given any number n, then one way to find its factors is to get its square root p:

sqrt(n) = p

Of course, if we multiply p by itself, then we get back n:

p*p = n

It can be re-written as:

a*b = n

Where p = a = b. If a increases, then b decreases to maintain a*b = n. Therefore, p is the upper limit.

Update: I am re-reading this answer again today and it became clearer to me more. The value p does not necessarily mean an integer because if it is, then n would not be a prime. So, p could be a real number (ie, with fractions). And instead of going through the whole range of n, now we only need to go through the whole range of p. The other p is a mirror copy so in effect we halve the range. And then, now I am seeing that we can actually continue re-doing the square root and doing it to p to further half the range.

Hyalite

Answer 10

Let n be non-prime. Therefore, it has at least two integer factors greater than 1. Let f be the smallest of n's such factors. Suppose f > sqrt n. Then n/f is an integer ≤ sqrt n, thus smaller than f. Therefore, f cannot be n's smallest factor. Reductio ad absurdum; n's smallest factor must be ≤ sqrt n.

Rearrange

explain with an example , this is not at all understandable – Bisayas

Answer 11

Any composite number is a product of primes.

Let say n = p1 * p2, where p2 > p1 and they are primes.

If n % p1 === 0 then n is a composite number.

If n % p2 === 0 then guess what n % p1 === 0 as well!

So there is no way that if n % p2 === 0 but n % p1 !== 0 at the same time. In other words if a composite number n can be divided evenly by p2,p3...pi (its greater factor) it must be divided by its lowest factor p1 too. It turns out that the lowest factor p1 <= Math.square(n) is always true.

Selfliquidating

If you curious why it is true @Kathernkatheryn explained the fact in its answer greatly. I added my answer because I had really hard times to visualize and understand other provided answers. It just didn't clicked. – Selfliquidating

Mate i trully believe that this is the correct answer. Everyone says about a=b*c but they dont mention that b & c are primes. So I was trying to figure out the answer and as you said, didnt click. Until i found your answer that makes everything clear! Thank you so much for this! Otherwhise, for the whole day I would have this question in my head! – Conatus

Answer 12

Yes, as it was properly explained above, it's enough to iterate up to Math.floor of a number's square root to check its primality (because sqrt covers all possible cases of division; and Math.floor, because any integer above sqrt will already be beyond its range).

Here is a runnable JavaScript code snippet that represents a simple implementation of this approach – and its "runtime-friendliness" is good enough for handling pretty big numbers (I tried checking both prime and not prime numbers up to 10**12, i.e. 1 trillion, compared results with the online database of prime numbers and encountered no errors or lags even on my cheap phone):

function isPrime(num) {
  if (num % 2 === 0 || num < 3 || !Number.isSafeInteger(num)) {
    return num === 2;
  } else {
    const sqrt = Math.floor(Math.sqrt(num));
    for (let i = 3; i <= sqrt; i += 2) {
      if (num % i === 0) return false;
    }
    return true;
  }
}

<label for="inp">Enter a number and click "Check!":</label><br>
<input type="number" id="inp"></input>
<button onclick="alert(isPrime(+document.getElementById('inp').value) ? 'Prime' : 'Not prime')" type="button">Check!</button>

Heinz

Answer 13

To test the primality of a number, n, one would expect a loop such as following in the first place :

bool isPrime = true;
for(int i = 2; i < n; i++){
    if(n%i == 0){
        isPrime = false;
        break;
    }
}

What the above loop does is this : for a given 1 < i < n, it checks if n/i is an integer (leaves remainder 0). If there exists an i for which n/i is an integer, then we can be sure that n is not a prime number, at which point the loop terminates. If for no i, n/i is an integer, then n is prime.

As with every algorithm, we ask : Can we do better ?

Let us see what is going on in the above loop.

The sequence of i goes : i = 2, 3, 4, ... , n-1

And the sequence of integer-checks goes : j = n/i, which is n/2, n/3, n/4, ... , n/(n-1)

If for some i = a, n/a is an integer, then n/a = k (integer)

or n = ak, clearly n > k > 1 (if k = 1, then a = n, but i never reaches n; and if k = n, then a = 1, but i starts form 2)

Also, n/k = a, and as stated above, a is a value of i so n > a > 1.

So, a and k are both integers between 1 and n (exclusive). Since, i reaches every integer in that range, at some iteration i = a, and at some other iteration i = k. If the primality test of n fails for min(a,k), it will also fail for max(a,k). So we need to check only one of these two cases, unless min(a,k) = max(a,k) (where two checks reduce to one) i.e., a = k , at which point a*a = n, which implies a = sqrt(n).

In other words, if the primality test of n were to fail for some i >= sqrt(n) (i.e., max(a,k)), then it would also fail for some i <= n (i.e., min(a,k)). So, it would suffice if we run the test for i = 2 to sqrt(n).

Perk

There are much shorter and IMHO much easier to understand and more on-topic explanations in the comments and the 6 years old answers... – Prady