C Program to check whether given number is prime or not.

// C Program to check whether given number is prime or not.

#include <stdio.h>
    int main()
    {
        int n, i, flag = 0;
        printf("Enter a positive integer: ");
        scanf("%d", &n);
        for(i = 2; i <= n/2; ++i)
        {
            // Condition for Nonprime number
            if(n%i == 0)
            {
                flag = 1;
                break;
            }
        }
        if (n == 1) 
        {
          printf("1 is neither a prime nor a composite number.");
        }
        else 
        {
            if (flag == 0)
              printf("%d is a prime number.", n);
            else
              printf("%d is not a prime number.", n);
        }
        
        return 0;
    }

Output :
Enter a positive integer: 29
29 is a prime number.


Description :

What is Prime Number?

  • A prime number is a whole number greater than 1 whose only factors are 1 and itself.
  • A prime number is a natural number greater than 1 that cannot be formed by multiplying two smaller natural numbers.
  • A natural number that is not prime is called a composite number.
  • The first few prime numbers are 2, 3, 5, 7, 11, 13, 17, 19, 23, …
  • The number 1 is neither prime nor composite.

Logic to check prime number

If a number (n) is not divisible by any integer number between 2 to n-1 then we can say that n is prime number else n is not prime or composite number.

  1. Let’s declare a variable called flag and initialize it with 1 to indicate that n is prime.
  2. Now, iterate a loop from 2 to n-1.
  3. If n is divisible by any number between 2 to n-1 then set flag to 0 which indicates that n is not prime.
  4. If n is not divisible by any number then flag remains unchanged which indicates that n is prime.

Caution

Most of the time, programmer especially student get confused between even or odd program and prime number program. You can check number for even or odd by only one modulo operation but to check for primality, we have to iterate 2 to n-1 times.

Optimization

Instead of n-1, we can iterate up to n/2 also because no number between n/2 to n-1 can divide n. thus 50% (half) iterations are reduced.

If we use break when n is divisible then we save further iterations because once n is divided it means it can’t be prime number.



Leave a comment