C Program to Generate Prime Numbers up to a Limit n

Here's a C program with output and explanation to generate prime numbers up to a limit n using Modulus, IF-Else condition, For Loop and GOTO Statement.

# include <stdio.h>
# include <conio.h>
void main()
{
int i, j, n ;
clrscr() ;
printf("Enter the limit : ") ;
scanf("%d", &n) ;
printf("\nThe prime numbers are :\n\n") ;
for (i = 1 ; i <= n ; i++)
{
if(i == 1)
{
goto loop ;
}
if(i == 2 || i == 3)
{
printf("%d\t", i) ;
}
else
{
for (j = 2; j <= i / 2 ; j ++)
{
if (i % j == 0)
goto loop ;
}
printf("%d\t", i) ;
loop : ;
}
}
getch() ;
}

Output of above program -

Enter the limit : 10
The prime numbers are :

2        3        5        7 

Explanation of above program -

Let's understand the above program to generate prime number with the help of an example.

Let the value of limit n be 10. Now the program enters in the for loop. So let's look at the working of loop iteration by iteration.

Working of outer for loop -

The for loop iterates for the value of loop variable i = 1 to n, incrementing the value of i after each iteration. Inside the loop, first statement is an IF-Else condition which checks whether the value of i is less than or equal to 3 or not. The purpose of this IF-Else condition is to improve performance as we already know that 1, 2 and 3 are the first three prime numbers so we don't need to do extra computations for these three numbers. In the IF part we print the values of i if i = 1 or 2 or 3. Otherwise else part is executed.

Inside else, there's another for loop which calculates other prime numbers up to the limit n.

Working of Inner for loop -

The inner for loop does the calculation of prime numbers. The loop runs for the value of loop variable j = 2 to i / 2 (i is the loop variable of outer for loop).

Note: To check for a prime number we just need to check whether a number i is divisible by any number between 2 and i / 2. It is obvious because no number can be divisible by a number which is greater than its half e.g. all divisors of 18 are less than or equal to 9 i.e. half of 18. This is also true for each number. So we can reduce our for loop by half number of total iterations. Also, we can skip the checking for 1, 2 and 3 using the IF condition, setting the flag variable to 0 i.e. that number is a prime number.

Inside this loop we just check whether a number i is completely divisible by any number within the range 2 to i / 2. If the number is divisible by any number within this range the program, with the help of a goto statement skips the inner loop and continue to check next number. If the number is a prime number i.e. not divisible by any number within that range, the value of that number is printed and the program continues to find other prime numbers.

Suppose the limit n is 10. So the outer loop will run for i = 1 to 10.

For i = 1, 2, 3 -

• The program simply prints the value of i as for these values of i the IF condition becomes true.

For i = 4 -

• Else part is executed.
• The inner for loop is executed for j = 2 to i / 2 (4/2 = 2). So the inner loop is executed only once.
• Inside the loop, the IF condition is executed because i % j = 4 % 2 = 0. So this number is not a prime number.
• Finally, goto statement ends the inner loop and the program continues with the next value of i.

For i = 5 -

• Else part is executed.
• The inner for loop is executed for j = 2 to i / 2 (5/2 = 2). So the inner loop is executed only once.
• Inside the loop, the IF condition becomes false because i % j = 5 % 2 = 1. Hence the number is a prime number.
• So using the next printf() the value of this number is printed and the program continues with the next value of i.

For i = 6 -

• Else part is executed.
• The inner for loop is executed for j = 2 to i / 2 (6/2 = 3). So the inner loop is executed twice i.e. for j = 2 and 3.
• Inside the loop, the IF condition is executed because i % j = 6 % 2 = 0. So this number is not a prime number.
• Now, goto statement ends the inner loop prematurely and the program continues with the next value of i.
• Note that even though the inner loop should be executed twice, the appearance of a goto sends the program flow outside the inner loop. This is good from the performace point of view as we already know that the number is not prime in the early stages of computation so we can skip the rest of the computation.

For i = 7 -

• Else part is executed.
• The inner for loop is executed for j = 2 to i / 2 (7/2 = 3). So the inner loop is executed twice.
• Inside the loop, the IF condition becomes false because i % j = 7 % 2 = 1. So the loop continues with the next value of j i.e. 3.
• Again, the IF condition becomes false because i % j = 7 % 3 = 1. Hence the number is a prime number.
  
• So using the next printf() the value of this number is printed and the program continues with the next value of i.

For i = 8 - 

• Else part is executed. 
• The inner for loop is executed for j = 2 to i / 2 (8/2 = 4). So the inner loop is executed three times i.e. for j = 2, 3 and 4.
• Inside the loop, the IF condition is executed because i % j = 8 % 2 = 0. So this number is not a prime number.
• Now again, goto statement ends the inner loop prematurely and the program continues with the next value of i.

For i = 9 - 

• Else part is executed. 
• The inner for loop is executed for j = 2 to i / 2 (9/2 = 4). So the inner loop is executed three times i.e. for j = 2, 3 and 4.
• Inside the loop, the IF condition becomes false because i % j = 9 % 2 = 1. So the loop continues with the next value of j i.e. 3.
• Now, the IF condition is executed because i % j = 9 % 3 = 0. So this number is not a prime number.
• Now again, goto statement ends the inner loop prematurely and the program continues with the next value of i. 

For i = 10 - 

• Else part is executed. 
• The inner for loop is executed for j = 2 to i / 2 (10/2 = 5). So the inner loop is executed four times i.e. for j = 2, 3, 4 and 5.
• Inside the loop, the IF condition is executed because i % j = 10 % 2 = 0. So this number is not a prime number.
  
• Now again, goto statement ends the inner loop prematurely and the program continues with the next value of i. 

 This is how the program works and computes the prime number.

Tip: To understand the program you can also take different values of n and try the above process yourself. It will help you to understand the process  much clearly and helps in improving your debugging ability.