Logic:
- 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)
Program to 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