A program which determines if a given number is prime or not

[Gondvanaz]

Hi. So... basically i can't understand why the program "thinks" 2 is a prime number. I mean... i know that 2 is a prime number but i can't get why the program thinks it is a prime number. Look at the comments.

  #include <stdio.h>
int main(void)
{
	int num, i, x;
	printf ("Enter the number to test: ");
	scanf_s ("%d", &num); /*I type in 2*/
	x = 1;
	for (i = 2; i <= num / 2; i = i + 1) /* i = 2; 2 <= 2/2; FALSE (because 2 <= 1 */
		if ((num % i) == 0) x = 0;       /* if ((2 % 2) == 0) x = 0;*/
	if (x == 1) printf ("The number is prime. "); /*after all x is 0 which means it has to be a composite number however after running the program i get a result which determines 2 as a prime number*/
	else	printf ("The number is composite. ");
	return 0;
}

[Yanson]

when you enter 2 the for loop doesn't execute.

the expression (i <= num / 2) or (2 <= 1) fails

[Gondvanaz]

Would you say me what happens next? When i type in 2, the for loop fails... OK... then does the program execute if ((num % i) == 0) x = 0; or it directly assigns x == 1 to the given number? Does every number which fails directly gets x == 1 i.e. every number which fails basically is a prime number?

[Yanson]

then does the program execute if ((num % i) == 0) x = 0;

no if ((num % i) == 0) x = 0; doesn't execute because the for loop fails.

if (x == 1) is executed next

x is given the value of 1 on line 7. So when the for loop fails the first time x is equal to 1.

[Gondvanaz]

Thanks for the explanation. Just one more question:
What happens with the increment i = i + 1 when the result of for (i = 2; i <= num / 2; i = i + 1) is true?
For example i type in 10.The condition for (i = 2; i <= num / 2; i = i + 1) is true. The program executes if ((num % i) == 0) x = 0; and finally ascertain the fact that 10 is a composite number. OK. But what about the increment i = i + 1? Next time when i test a number, will it be i = 2 + 1 = 3?

Also why do we divide num to 2? What is the purpose of it? Is it because 2 is the smallest prime number?

[Yanson]

Next time when i test a number, will it be i = 2 + 1 = 3?
Yup it is equivalent to ++i;

Also why do we divide num to 2? What is the purpose of it?

This is an optimization and isn't strictly necessary. If you don't find a prime number before you reach half the target number. then you won't.

[Gondvanaz]

Next time when i test a number, will it be i = 2 + 1 = 3?
Yup it is equivalent to ++i;

But virtually i can't type in a second number to test because after the execution of 10 (for example) the program terminates and writes out "Press any key to continue..." This makes the increment i = i + 1 kinda pointless? Why do i need it after it will never get i = 3?

[keskiverto]

It is easy to test:

#include <cstdio>

int main()
{
  int num = 7;
  int x;
  for ( x = 2; x <= num / 2; x = x + 1) {
    printf( "within loop: %d\n", x);
  }

  printf( "After loop: %d\n", x);
  return 0;
}

Produces:

within loop: 2
within loop: 3
After loop: 4

In other words,
1. The loop first initializes x with with value 2
2. Since 2 <= 3 (remember: 7/2==3) the loop body prints "within loop: 2" and x is incremented to 3
3. Since 3 <= 3 the loop body again prints "within loop: 3" and x is incremented to 4
4. The 4 <= 3 is not true and the loop ends without changing the x any more.
5. Line 11 prints "After loop: 4"

Note that

  for ( x = 2; x <= num / 2; x = x + 1) {
    printf( "within loop: %d\n", x);
  }

could be written

  for ( x = 2; x <= num / 2; ) {
    printf( "within loop: %d\n", x);
    x = x + 1;
  }

and also

  x = 2;
  while (  x <= num / 2 ) {
    printf( "within loop: %d\n", x);
    x = x + 1;
  }

Further note that there is are compound assignment operators. += is one of them.
Furthermore, there are pre- and post-increment and -decrement operators.

The following three lines do the same operation:

x = x + 1;
x += 1;
++x;

Why divide num by 2?

The loop tests whether value i is a divisor of num.
How many values are there that are larger than num/2 and can divide num?
Num itself, of course, because num/num==1, but are there other values?
If there were such value X, then num/X must be less than 2 but more than 1 and there is no such integer.

In other words: we know analytically that it is pointless to test values that are greater than num/2.