Prime number Logic, n/2 condition in a loop

Question

The following code is for prime number. I want to know why we use i<=n/2 condition in the loop.

C Program:

#include <stdio.h>
int main()
{
int n, i, flag = 0;

printf("Enter a positive integer: ");
scanf("%d",&n);

for(i=2; i<=n/2; ++i)
{
    // condition for nonprime number
    if(n%i==0)
    {
        flag=1;
        break;
    }
}

if (flag==0)
    printf("%d is a prime number.",n);
else
    printf("%d is not a prime number.",n);

return 0;
}

Also it is more about reverse engineering of some code OP found than about actual problem solving :D — Vlasec, Oct 26 '17 at 16:41
To be fair, [the site where this code is copied from](https://www.programiz.com/c-programming/examples/prime-number) doesn't do a very good job of explaining it. — Bill the Lizard, Oct 26 '17 at 16:45
I don't know why the code uses `n/2`, especially since you only need to check factors up to the square root of a number to determine prime-ness. — azurefrog, Oct 26 '17 at 16:47

Rakesh Soni · Accepted Answer · 2017-10-26T16:59:52.733

Although this is C program. But prime number logic will be same for C and Java both

Prime number
Each natural number that is divisible only by 1 and itself is prime. Also, 2 is the first prime number.

For example, we want to test that number 100 is a prime number or not. we can do a trial division to test the primality of 100.

Let's look at all the divisors of 100:

2, 4, 5, 10, 20, 25, 50

Here we see that the largest factor is 100/2 = 50. This is true for all n: all divisors are less than or equal to n/2.

So here condition i<=n/2 condition is correct. Since we need to test divisors up to n/2 only.

Please check the Wiki link for more detail https://en.wikipedia.org/wiki/Primality_test

Second example

Similarly, for 11 you would check all integers smaller than 5.5, i.e. 1, 2, 3, 4 and 5.

To find a number is prime, Why checking till n/2 is better. What is the reason for avoiding numbres in second half of n

I see your link about n/2, and raise you with [the one about sqrt](https://stackoverflow.com/questions/5811151/why-do-we-check-up-to-the-square-root-of-a-prime-number-to-determine-if-it-is-pr). — Will Ness, Oct 28 '17 at 16:17

score -1 · Answer 2 · answered Sep 15 '18 at 23:14

-1

The largest factor for any number n must be <= n/2, so no need to check the bigger numbers

answered Sep 15 '18 at 23:14

Ibrahim El_Khatib

453
6
11

[See this](https://stackoverflow.com/q/5811151/1364007). Technically you're not wrong, but you're not as right as you could be. – Wai Ha Lee Sep 16 '18 at 00:00
@WaiHaLee I saw that, it is about another way to get the limit of the loop to check prime number in more efficient way, but it has no thing with this particular question, the question is about clarification of n/2 not what is the best way to get prime numbers :) – Ibrahim El_Khatib Sep 16 '18 at 07:23

Prime number Logic, n/2 condition in a loop

2 Answers2

Linked