Prime Number Program in C | Program for Prime Number in C

 

Program to check a single number is prime or not in c:

In this program, we will take input from the user and check whether the given input number is prime or not.

C

1

#include<stdio.h>  

2

int main(){    

3

int n,i,m=0,flag=0;    

4

printf("Enter the number to check prime:");    

5

scanf("%d",&n);    

6

m=n/2;    

7

for(i=2;i<=m;i++)    

8

{    

9

if(n%i==0)    

10

{    

11

printf("Number is not prime");    

12

flag=1;    

13

break;    

14

}    

15

}    

16

if(flag==0)    

17

printf("Number is prime");     

18

return 0;  

19

 }    

Output:

C Program to check given number is prime or not using for loop:

In this program, we will ask the user to input n number and check whether the given n number is prime or not using for loop.

C

1

#include <stdio.h> 

2

main() 

3

{

4

  int n, i, c = 0;

5

  printf("Enter any number n to check:");

6

  scanf("%d", &n);

7

  for (i = 1; i <= n; i++) 

8

  {

9

      if (n % i == 0) 

10

      {

11

         c++;

12

      }

13

  }

14

  if (c == 2) 

15

  {

16

  printf("given n is a Prime number");

17

  }

18

  else 

19

  {

20

  printf("given n is not a Prime number");

21

  }

22

  return 0;    

23

}

Output:

Explanation:

let us consider n=5 for loop becomes for(i=1; i<5; i++)

1st Iteration: for(i=1; i<=5; i++) in 1st iteration i is incremented i.e the value of i for the next iteration is 2.If (n%i==0) then c is incremented i.e (5%1==0) then c is incremented.Here, (5%1=0) so c is incremented i.e c=1.

2nd Iteration: for(i=2;i<=5;i++) in 2nd iteration i is incremented i.e the value of i for the next iteration is 3.If (n%i==0) then c is incremented i.e (5%2==0) then c is incremented.here,(5%2!=0) so c is not incremented i.e c=1.

3rd Iteration: for(i=3;i<=5;i++) in 3nd iteration i is incremented i.e the value of i for the next iteration is 4.If (n%i==0) then c is incremented i.e (5%3==0) then c is incremented.Here,(5%3!=0) so c is not incremented i.e c=1.

4th Iteration: for(i=4;i<=5;i++) in 4th iteration i is incremented i.e the value of i for the next iteration is 5.If (n%i==0) then c is incremented i.e (5%4==0) then c is incremented.Here,(5%4!=0) so c is not incremented i.e c=1.

5th Iteration: for(i=5;i<=5;i++) in 5th iteration i is incremented i.e the value of i for the next iteration is 6.If (n%i==0) then c is incremented i.e (5%5==1) then c is incremented.Here,(5%5=0) so c is incremented i.e c=2.

6th Iteration: for(i=6;i<=5;i++) in 6th iteration the value of i is 6 which is greater than n i.e i>n(6>5) so the for loop is terminated.Here c=2 so the given number is prime number.

C Program to check given number is prime or not using while loop:

In this program we will ask user to enter the number which user want to check whether it is prime or not and then check it using while loop.

C

1

#include <stdio.h> 

2

int main()

3

{

4

int i = 2, Number, count = 0; 

5

printf("\n Please Enter number to Check Prime or not \n");

6

scanf("%d", &Number);

7

while(i <= Number/2)

8

   {

9

     if(Number%i == 0)

10

     {

11

   count++;

12

    break;

13

      }

14

      i++;  

15

   }

16

   if(count == 0 && Number != 1 )

17

   {

18

    printf("\n %d is a Prime Number", Number);

19

   }

20

   else

21

   {

22

    printf("\n %d is Not a Prime Number", Number);

23

   }

24

  return 0;

25

}

Output:

In above program we just replace the for loop instead we add while loop.

C program to check the given number is prime or not using functions:

In this program, we will use the function find_factors to check whether the given number is prime or not.

C

1

#include <stdio.h>

2

int find_factors(int Number)

3

{ 

4

  int i, Count = 0; 

5

  for (i = 2; i <= Number/2; i++)

6

   {

7

    if(Number%i == 0)

8

     {

9

       Count++;

10

     } 

11

   }

12

   return Count;

13

}

14

int main()

15

{

16

  int i, Number, count = 0;  

17

  printf("\n Please Enter any number to Check Prime or not \n");

18

  scanf("%d", &Number);

19

  count = find_factors(Number);

20

   if(count == 0 && Number != 1 )

21

   {

22

    printf("\n %d is a Prime Number", Number);

23

   }

24

   else

25

   {

26

    printf("\n %d is Not a Prime Number", Number);

27

   }

28

  return 0;

29

}

Output:

Sieve Of Eratosthenes Algorithm:

In this algorithm, we first declare the numbers from [2:n]. We mark all the multiples of 2 as the number 2 is composite. A proper multiple of number x, which is multiple of number x and divisible by x.

Then we mark the number which hasn’t be composite.for example 3 which is not composite,It means that 3 is a prime number.

Now we will see the program for Sieve Of Eratosthenes Algorithm.

C

1

int count_primes(int n) {

2

    const int S = 10000;

3

    vector<int> primes;

4

    int nsqrt = sqrt(n);

5

    vector<char> is_prime(nsqrt + 1, true);

6

    for (int i = 2; i <= nsqrt; i++) {

7

        if (is_prime[i]) {

8

            primes.push_back(i);

9

            for (int j = i * i; j <= nsqrt; j += i)

10

                is_prime[j] = false;

11

        }

12

    }

13

    int result = 0;

14

    vector<char> block(S);

15

    for (int k = 0; k * S <= n; k++) {

16

        fill(block.begin(), block.end(), true);

17

        int start = k * S;

18

        for (int p : primes) {

19

            int start_idx = (start + p - 1) / p;

20

            int j = max(start_idx, p) * p - start;

21

            for (; j < S; j += p)

22

                block[j] = false;

23

        }

24

        if (k == 0)

25

            block[0] = block[1] = false;

26

        for (int i = 0; i < S && start + i <= n; i++) {

27

            if (block[i])

28

                result++;

29

        }

30

    }

31

    return result;

32

}

Here we have a program that counts the no of primes smaller than or equal to n.