CODEWITHSUNDEEP
cif-statementprimality-test
Sheshadri Iyengar
Sheshadri Iyengar

Reputation: 51

Using an If statement to find prime numbers

The following is a piece of code that shows an output stating whether a number, entered by a user, is a prime number or not.

#include <stdio.h>
#include <stdlib.h>

int a,b;
int main(void) {

 printf("Enter number: ");
 fflush(stdout);
 scanf("%d",&a);

 for (b = 2; b < a; b++)
 {
   if (a % b == 0)
    break;
 }

 if (b<a)
 {
   printf ("%d is divisible by %d\n", a, b);
 }

 else
 {
   printf ("%d is prime \n", a);
 }
return 0;
}

The piece of code, written above, is not mine and it identifies a prime number successfully everytime (i.e the printf statement of the else clause gets printed).

My understanding of the if statement is that an else clause in an if-else statement belongs to the nearest if statement which doesn't already have an else clause. And so, having said that, I believe the else clause, in the above piece of code, belongs to the nearest if statement.

My question is this: If the user enters a prime number like 31 or 37 or any other prime number, how does the printf statement of the else clause get printed? The condition if (b<a) (of the second if statement) will always be true considering that b will only be incremented to (a-1). And so if the user enters the number 31, the variable b will only be incremented to 30. Shouldn't it be the case that the printf statement of the second if statement gets printed, regardless of whether the number entered by the user is prime or not, considering that the condition if (b<a) will always be true?

How does the above piece of code print all the prime numbers correctly, and therefore, work alright? (when, according to my limited understanding of the way the if statement works, it shouldn't)

Upvotes: 1

Views: 10467

Answers (3)

Vlad from Moscow
Vlad from Moscow

Reputation: 310930

This loop

for (b = 2; b < a; b++)
{
  if (a % b == 0)
   break;
}

can be interrupted in two cases. The first one is when a is divisible by b

  if (a % b == 0)
   break;

But for prime numbers this condition is always will be equal to false.

So the other case when the loop will be interrupted is when b after increment 

for (b = 2; b < a; b++)
                   ^^^

will became equal to a. In this case the condition

for (b = 2; b < a; b++)
            ^^^^^

will be equal to false and the control will be passed to the if-else statement. If so then b is equal to a and a is a prime number.

Upvotes: 2

Andrew Cheong
Andrew Cheong

Reputation: 30273

First, you are correct, the whitespace between

if (b<a)
{
    ...
}

and

else
{
    ...
}

doesn't matter. The else indeed belongs to the if.

Second, it's not true that the if (b<a) is always true. As long as a % b == 0 never returned true, the loop continues until b==a, which fails the condition. They could have also written if (b!=a).

Upvotes: 1

Mat
Mat

Reputation: 206679

The condition if (b<a) (of the second if statement) will always be true considering that b will only be incremented to (a-1).

That is not the case. If no divisor is found, the for loop continues until the condition b<a is false. This happens when b == a, not b == a-1. The loop body isn't run when the loop condition is false, but the increment has happened nevertheless.

Upvotes: 4

Related Questions