Prime Number A number is prime if it is divisible by 1 and the number itself only.
Enter the number n
Example 1: n=15
We will check whether number is divisible by any number from 2 to n-1 here 14.
If it is divisible by any number (example 15 is divisible by 3) , then It is not prime number. And We dnt need to check further divisibility from 4 to 14.
Example 2: n=5
We will check whether number is divisible by any number from 2 to n-1 here 4.
Since 5 is not divisible by any numbers 2, 3, 4 . So It is a prime number.
Algorithm
Enter the number as n
for(i=2;i<=n-1;i++)
{
if(n%i==0)
{
printf(“It is not prime”);
break;
}
}
if(i==n)
printf(“It is prime”);
Time Complexity: O(n)
Space Complexity: O(1)
Programto check a number for Prime (Without Function)
#include <stdio.h>
int main()
{ printf("****************************************************************");
printf("\n****************************************************************");
printf("\n** WAP to check a number for prime **");
printf("\n** Created by Sheetal Garg **");
printf("\n** Assistant Professor **");
printf("\n** Phone No:9467863365 **");
printf("\n****************************************************************");
printf("\n****************************************************************\n");
int n,i;
printf("enter number");
scanf("%d",&n);
for(i=2;i<=n-1;i++)
{
if(n%i==0)
{
printf("It is not prime");
break;
}
}
if(i==n)
printf("It is prime");
return 0;
}
Output 1
***************************************************************************
***************************************************************************
** WAP to check a number for prime **
** Created by Sheetal Garg **
** Assistant Professor **
** Phone No:9467863365 **
***************************************************************************
***************************************************************************
enter number
15
It is not prime
Output 2
***************************************************************************
***************************************************************************
** WAP to check a number for prime **
** Created by Sheetal Garg **
** Assistant Professor **
** Phone No:9467863365 **
***************************************************************************
***************************************************************************
enter number
5
It is prime
Program to check a number for Prime (Using Function)
#include <stdio.h>
char check_prime(int n);
int main()
{
printf("******************************************************\n");
printf("******************************************************\n");
printf("** WAP to check a number for prime using function **\n");
printf("** Created by Sheetal Garg **\n");
printf("** Assistant Professor **\n");
printf("** Phone No:9467863365 **\n");
printf("******************************************************\n");
printf("******************************************************\n");
int n;
char result;
printf("\nenter number\n");
scanf("%d", &n);
result = check_prime(n);
if (result == 'T')
printf("\nIt is prime");
else
printf("\nIt is not Prime");
return 0;
}
char check_prime(int n)
{
int i;
for (i = 2; i <= n - 1; i++)
if (n % i == 0)
return 'F';
return 'T';
}
Output 1
******************************************************
******************************************************
** WAP to check a number for prime using function **
** Created by Sheetal Garg **
** Assistant Professor **
** Phone No:9467863365 **
******************************************************
******************************************************
enter number
5
It is prime
Output 2
******************************************************
******************************************************
** WAP to check a number for prime using function **
** Created by Sheetal Garg **
** Assistant Professor **
** Phone No:9467863365 **
******************************************************
******************************************************
enter number
15
It is not prime
Program to print Prime Numbers between 1 and n (Using Function)
#include <stdio.h>
char check_prime(int n);
int main()
{
printf("******************************************************\n");
printf("******************************************************\n");
printf("** WAP to check a number for prime using function **\n");
printf("** Created by Sheetal Garg **\n");
printf("** Assistant Professor **\n");
printf("** Phone No:9467863365 **\n");
printf("******************************************************\n");
printf("******************************************************\n");
int n,i;
char result;
printf("\nenter number upto which you want to print prime numbers\n");
scanf("%d", &n);
printf("Prime numbers upto %d are : ",n);
for(int i=1;i<n;i++)
{
result = check_prime(i);
if (result == 'T')
printf("%d ",i);
}
return 0;
}
char check_prime(int n)
{
int i;
for (i = 2; i <= n - 1; i++)
if (n % i == 0)
return 'F';
return 'T';
}
Output 1
******************************************************
******************************************************
** WAP to check a number for prime using function **
** Created by Sheetal Garg **
** Assistant Professor **
** Phone No:9467863365 **
******************************************************
******************************************************
enter number upto which you want to print prime numbers
50
Prime numbers upto 50 are : 1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
Output 2
******************************************************
******************************************************
** WAP to check a number for prime using function **
** Created by Sheetal Garg **
** Assistant Professor **
** Phone No:9467863365 **
******************************************************
******************************************************
enter number upto which you want to print prime numbers
35
Prime numbers upto 35 are : 1 2 3 5 7 11 13 17 19 23 29 31