I wonder what's the explanation of the for loop for(i=2; i<=Number/2; i++)

Question

Hi I have a code for getting prime numbers from a specific range, I'm analyzing it since its from the internet, I just wonder what the for loop for(i=2; i<=number/2; i++);. Why does it start with two and what's the reason behind why i<=number/2 is the condition. Here is the full code below, I hope you can help me.

#include <stdio.h>
 
int main()
{
  int i, Number, count, Minimum, Maximum; 

  printf("\n Please Enter the Minimum & Maximum Values\n");
  scanf("%d %d", &Minimum, &Maximum);
 
  printf("Prime Numbers Between %d and %d are:\n", Minimum, Maximum);  
  for(Number = Minimum; Number <= Maximum; Number++)
  {
    count = 0;
    for (i = 2; i <= Number/2; i++)
    {
      if(Number%i == 0)
      {
    count++;
    break;
      }
    }
    if(count == 0 && Number != 1 )
    {
       printf(" %d ", Number);
    }  
  
  }
  return 0;
}

Answer 1

2 is the lowest possible factor of a composite (1 is a factor of primes, remember).

Number/2 is an upper bound for the smallest factor. I say an upper bound, because a better bound would be sqrt(Number). Reasoning: any factor p that's greater than √N must have a corresponding factor q = N/p which must be less than √N.

Answer 2

for (Number = Minimum; Number <= Maximum; Number++)
# This for loop is traversing all numbers in the range of the minimum and maximum number

for (i = 2; i <= Number / 2; i++)
# This for loop is checking if the number is divisible by any number starting from 2

For example, this can be used checking if number is prime number.

Take i <= Number / 2 as the loop condition.

If Number = 11 then this for loop will begin diving the number starting from 2. So the value of i will go from 2 to Number / 2, which is 5.

This improves the performance of the loop by reducing the amount of required iterations.

Answer 3

Why does it start with two and what's the reason behind why i<=number/2

That lower and upper bound is about performance i.e., reducing the number of iterations that you need to compute.

It starts in 2 because:

A prime number (or a prime) is a natural number greater than 1

It ends in Number/2 because if Number is a prime number until Number/2 then after that will still be a prime number.

The reason is as follows, "If a number n is not a prime, it can be factored into two factors" so that Number = a * b. So either a or b has to be at least 2 or larger. Therefore, you can set the upper bound to Number/2.

From prime number theory we know that actually if Number is a prime number until sqrt(Number) then it will still be a prime number after. From source one can read:

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 smaller than 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.

Answer 4

for loops must follow a specific structure.

The first statement (i=2) states that the counter must start at 2. The second statement (i <= Number/2) means the loop will continue whilst that statement is true. The final statement (i++) increments the variables i by 1 each time the loop runs.

So in this example, i starts at 2, then will increase by 1 each time until i is greater than Number before continuing to the remainder of the program.

Answer 5

First, 2 is the lowest factor of a composite while Number/2 is the highest limit in the condition starting from 2 to Number/2. We can stop at Number/2 because if Number is prime until then it will still remain prime after Number/2 to Number as well.

The point of using such limits is to improve performance by reducing loop count.