8

To check if a number is prime or not, the naive way is to try dividing the number by 2 thru n, and if any operation gets remainder as 0, then we say the given number is not prime. But its optimal to divide and check only till n/2 (am aware much better way is till sqrt(n) ), I want to know the reason for skipping the second half.

say if we need to check number 11 is prime or not, 11/2 = 5. if we do 11/6 or 11/7 or 11/8 or 11/9 or 11/10 in neither of these cases we get remainder as 0. So is the case for any given number n.

Is the reason for avoiding second half this? "if you divide the given number by any number which is more than given number's half, remainder will never be 0 Or in other words, none of the numbers which are more than the given number's half can divide the given number"

Please help me know if am right

Venkatesh Kolla - user2742897
  • 333
  • 2
  • 4
  • 12
  • 2
    Actually, you can escape more than the second half. :) But, imagine that you have a number x. It can be divided by 2, 3, ..., x/2 . And that's all if you don't consider 1 and x. `x % y = 0` <=> `x = y * z`, but if you take `y > x/2` => `z < 2` and the only integer `0 < z < 2` is `1`. So, you don't care about it, because every number `x = x * 1`. – ROMANIA_engineer Sep 10 '16 at 19:03
  • yes you are right. One might say the root of the number is might be enough. – ali srn Sep 10 '16 at 19:05
  • No point checking past SQRT(n) beacause if any number in that range divides into n then the remainder will be less than SQRT(n) and will have already been checked. – Fruitbat Sep 10 '16 at 19:09
  • Thank you @ROMANIA for explaining it in mathematical way. It made me more clear. – Venkatesh Kolla - user2742897 Sep 10 '16 at 19:17
  • 1
    I’m voting to close this question because it is a question about mathematics and not about programming. – n. m. could be an AI Jul 01 '22 at 05:24

5 Answers5

12

Because, the smallest multiple that will not make it a prime is 2. If you have checked all the numbers from 0 to n/2, what multiple is left that could possibly work? If multiple by 2 is bigger than n, then a multiple of 3 or 4 etc will also be bigger than n.

So the largest factor for any number N must be <= N/2

So yes take N/2, and check all integers smaller or equal to N/2. So for 11 you would check all integers smaller than 5.5, i.e. 1, 2, 3, 4 and 5.

The square root is explained here: Why do we check up to the square root of a prime number to determine if it is prime?

And this question has been asked before.

Aditya
  • 33
  • 6
PaulD
  • 1,161
  • 1
  • 9
  • 14
6

To factor the number n you have to divide by two other integers, call them a and b. Both of those numbers need to be 2 or larger, so it doesn't make any sense to check numbers larger than n/2, they couldn't possibly divide evenly.

And yes, sqrt(n) is more efficient, because if a is larger than sqrt(n) then b must be smaller, and you'd have already checked it.

Mark Ransom
  • 299,747
  • 42
  • 398
  • 622
0

Aim- To show that the factors of a composite number (excluding 1 and the number itself) belong to the set {2, 3, 4, 5, 6....., [n/2]}, where [] denotes Greatest Integer Function.

Proof:

Suppose the composite number to be n. Let it be expressed as a product of two factors a, b (both not equal to 1 or n, since we know for sure that 1 and n both will divide n therefore the smallest natural number that a and b could be is 2).

 n=a x b

Let us suppose that a>[n/2].

 Then  b=n/a this implies that b<2

(e.g. suppose n=39 then a>[39/2]=19. Suppose a is 20 (which is greater than 19) then b=39/20=1.95 which is not possible for the smallest possible value for both a and b both will be 2 (as per our assumption) since the conditions are not met for a=20 further increasing a will make b smaller and smaller than 2. In the same way, the thought process can be extended for all the composite numbers!)

This is not possible since the smallest natural number a and b could be is 2.

Therefore, our supposition was wrong, hence a and b both must belong to the set {2, 3, 4, 5, 6....., [n/2]}.

Parth Yadav
  • 35
  • 7
0

let's take a number n... of course, if it's a natural number and non-prime, It will be a multiplication of 2 numbers... let's say numbers are a and b so, n=ab...where n>1 To determine if the n number is non-prime...a b both have to be bigger or equal to 2 and shorter than n itself... So, the lowest value of both a and b can be 2... let's say b=2... n=ab.. =>n=a2 (taking b=2...) =>n/2=(a2)/2 (dividing 2 in both sides) =>a=n/2...

So, for b to be the lowest 2, a can be the highest n/2 the more a gets bigger than n/2...the more b gets smaller than 2...but it breaks the rule... that's why we check if it is divisible by 2 to n/2 to determine whether a number is prime or not...

Fissy ThinG
  • 1
0

Hey I was stuck with the same question and I figured out something simple which probably answers this question. We can observe that for every even integer n, the second highest factor is always equal to n/2 and for every odd integer n, the second highest factor is always less than n/2. Therefore we are getting an idea that for checking whether a number is prime or not, we only need to check the divisibility of that number up till n/2 because after n/2, the very next factor is the number itself. So it is a wastage of time to just check for the second half where it is not possible for a factor to be present.

Now why n/2 plays the key role? Suppose n=a*b; where a & b are the factors of n. We can have two cases : Either a=2 (in case 'n' is even) or a=k (in case 'n' is odd, where 'k' is any number> 2).

we have b=n/a;

So b is either equal to n/2 ( if n is even, thus a=2) or,

b=n/k (where k>2). As k>2, b<n/2

From here we can clearly conclude that b will always be less than or equal to n/2.

Anindo Choudhury
  • 1
  • 1