0

I know this question has been answered before, but I didn't quite understand the explanation that was given on that question.

I was doing the 30 days of code on HackerRank, and one of the exercises was to check whether a number is prime or not. Unfortunately, I was not capable of doing it by myself, so I checked the given solution after many attempts. Even after looking at the solutions, I can't understand one of the lines:

// Check for primality using odd numbers from 3 to sqrt(n)
for(int i = 3; i <= sqrt(n); i += 2){
    // n is not prime if it is evenly divisible by some 'i' in this range
    if( n % i == 0 ){ 
        isPrime = false;
    }
}

Why is sqrt(n) used in the for loop?

Will Ness
  • 70,110
  • 9
  • 98
  • 181
João Almeida
  • 57
  • 10
  • What was the explanation that you have read? What exactly didn't you understand? – mkrieger1 Dec 22 '19 at 01:43
  • 3
    consider a number larger than the square root, what would have to be true about its counterpart if it were a factor of the overall number? then consider one equal to the square root – anthony sottile Dec 22 '19 at 01:47
  • Take some particular n, for example n = 101. To make sure it's prime you have to make sure it's not divided by any number from 2 to 100. Now, what if you just check only odd numbers from 3 to 99? And finally, what if you just check odd numbers from 3 to 9? Do you need to check numbers starting 11 or it's enough and you can say 101 is prime? – Anatoliy R Dec 22 '19 at 01:53
  • The result of dividing `n` by any factor will be another factor. so for any factor `f`, the value `n/f` is another factor. If `f` is greater than the square root of `n`, then `n/f` must be less than the square root of `n`. – Peter Dec 22 '19 at 01:56
  • 1
    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), [Why do we only check up to the square root of a prime number to determine if it is prime? Can't we use cube root?](https://stackoverflow.com/q/41530090/995714) – phuclv Dec 22 '19 at 02:01

1 Answers1

4

Suppose n is a composite number.

Then, n = ab where a and b both are between 1 and n.

If a > sqrt(n) and b > sqrt(n), then this means that ab > sqrt(n)*sqrt(n) which basically implies that ab > n, this contradicts the assumption that ab = n.

Hence, either one factor (a or b) must be less than sqrt(n), or both be equal to it. So if n is composite, n must have a prime factor p <= sqrt(n)

r4bb1t
  • 1,033
  • 2
  • 13
  • 36