Prime number are those which are exactly divisible by itself and only 1. That means, prime number always have only two factors. All other number beside prime numbers are composite number. Note that, 1 is neither prime nor composite.

Logic of prime and composite

Since, prime number have only two factors, we divide given number by all the numbers from 1 to that number. Then, we count the total numbers which exactly divides the given number. This count gives total number of the factors of that given number. If it equals to 2 then the given number is prime else composite.

C program to check prime and composite

#include <stdio.h>
int main()
{
	int n, i, c=0, r;
	printf(“Enter any number”);
	scanf(“%d”, &n); 
	for(i=1; i<=n; i++)
	{
 		r=n%i;
 		if(r==0)
  		{
   			c=c+1;
  		}
	}
	if(c==2)
	{
 		printf(“%d is prime”, n);
	}
	else
	{
 		printf(“%d is composite”, n);
	}
	return 0;
}

In above program, if we enter 1 then it will result composite which is wrong. Since, 1 is neither prime nor composite we can solve this by using goto statement. If user enters 1 then this program will let user to enter another number beside 1.

#include <stdio.h>
int main()
{
	int n, i, c=0, r;
	label:
	printf(“Enter any number”);
	scanf(“%d”, &n);
	if(n==1)
	{
		printf(“1 is neither prime nor composite”);
		printf(“Enter another value beside 1”);
		goto label;
	} 
	for(i=1; i<=n; i++)
	{
 		r=n%i;
 		if(r==0)
 		{
  		c=c+1;
 		}
	}
	if(c==2)
	{
		printf(“%d is prime”, n);
	}
	else
	{
		printf(“%d is composite”, n);
	}
	return 0;
}

As in above we only check whether the given number prime or composite. But, if we want to display several prime number form 1 to any number than we will use same logic to find prime but we introduce nested for loop to display multiple prime numbers as follows:

C Program to display n - prime numbers

#include <stdio.h>
int main()
{
	int n, i, j, c=0, r;
	label:
	printf(“Enter any number”);
	scanf(“%d”, &n);
	if(n==1)
	{
		printf(“1 is neither prime nor composite”);
		printf(“Enter another value beside 1”);
		goto label;
	}
	for(j=1; j<=n; j++)
	{
		for(i=1; i<=j; i++)
		{
 			r=j%i;
 			if(r==0)
 			{
  				c=c+1;
 			}
		}
		if(c==2)
		{
			printf(“%d”, j);
		}
	c=0;
	}
	return 0;
}

Note: ‘n’ in above program can be directly changed to integer value such as 100, 500, 1000 so on.

Click here to go back to C main menu.