C program to check if a number is prime

A prime number is a number that can only be divided by the sum of two numbers themselves. A factor of a number is a number that divides the number.

The list of first ten prime numbers is 2,3,5,7,11,13,17,23,29,31.

Non-prime numbers are composite numbers. A composite number is a number that is divisible by two or more numbers.

If it is a prime number and a composite number, then 1 is neither a prime number nor a composite number because it is only divisible by itself.

How to check whether a number is prime or composite To check whether a number is prime, two conditions should be checked

1) It should be an integer greater than 1.

2) It should have only two factors, one and the number itself.

If these two conditions are met, then we can say that a number is prime.

In our program we will check that number divided by every number that is less than that number. A number is not prime if any number smaller than a given number is divisible by that number. Otherwise, it is prime.

Let us take two numbers as an example and use this procedure to check if they are prime numbers.

Input − Number1 − 42
Output − 42 is not a prime number

Logic - We divide 42 by every number greater than 1 and less than 42. Therefore,

42/2 = 21 i.e. 42 is divisible by 2, which means 42 is not a prime number because it is divisible by another number.

Input − Number2 − 7
Output − 7 is a prime number

Logic - We will divide 7 by every number greater than 1 and less than 7. So

7 is not divisible by 2 so the code will check the next number i.e. 3

7 is not divisible by 3 so the code will check the next number i.e. 4

7 is not divisible by 4 so the code will check the next number i.e. 5

>

7 is not divisible by 5 so the code will check the next number i.e. 6

7 is not divisible by 6 is divisible, which means that 7 is only divisible by 1, and 7 means that 7 is a prime number.

Look at the above logic, whether this number is 1000 plus or 100000 plus, then the program will iterate multiple times in the for loop, and this method will take a lot of calculation time. Therefore, in order to reduce the number of iterations, they must be better methods.

The optimized solution to this is to only run half the loop. This means that if the number is 77, the loop will only run to 38. This will reduce the number of iterations required, so we will use this algorithm to create the program.

Example

#include <stdio.h>
int main() {
   int num = 33, flag = 0;
   for(int i=2 ; i < num/2 ; i++) {
      if(num%i == 0) {
         printf("%d is not a prime number", num);
         flag = 1;
         break;
      }
   }
   if(flag == 0) {
      printf("%d is a prime number", num);
   }
}

Output

33 is a prime number

The above is the detailed content of C program to check if a number is prime. For more information, please follow other related articles on the PHP Chinese website!