A prime number is a number greater than 1 that cannot be formed by multiplying two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number.
The number 2 (Two) is the only even and the smallest prime number. Prime numbers have many applications in computer science and mathematics such as cryptography and abstract algebra.
First few prime numbers less than 100 are:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97
Source: OEIS
Below is the C program to check if a number is prime.
C program to check for Prime Number
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | #include <stdio.h> int main(void) { int n, lcv, flag; printf("Enter value of N > "); scanf("%d", &n); for (lcv=2, flag=1; lcv <= (n / 2); lcv++) { if ((n % lcv) == 0) { if (flag){ printf("The non-trivial factors of %d are: \n", n); } flag = 0; printf(" %d, ", lcv); } } if (flag){ printf("%d is prime\n", n); } } |
Output of the program is:
1 2 3 | Enter value of N > 36 The non-trivial factors of 36 are: 2, 3, 4, 6, 9, 12, 18, |
And
1 2 | Enter value of N > 11 11 is prime |
C program to check for Prime Number using function
We can slightly modify the above program to check for prime number using function.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | #include <stdio.h> int prime_number(int); int main(void) { int n, flag; printf("Enter value of N > "); scanf("%d", &n); flag = prime_number(n); if (flag==0){ printf("%d is prime\n", n); }else{ printf("%d is NOT prime\n", n); } } int prime_number(int n){ int lcv, flag; for (lcv=2; lcv <= (n / 2); lcv++) { if ((n % lcv) == 0) { return 1; } } return 0; } |
Output of the program is:
1 2 | Enter value of N > 19 19 is prime |
And
1 2 | Enter value of N > 25 25 is NOT prime |
C program to print all prime numbers less than 100
We can further modify the above program to print all of the primer numbers in the range of 2-100.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | #include <stdio.h> int prime_number(int); int main(void) { int n=2, flag=0; printf("Prime nmbers < 100 are: "); for (n=2;n<=100;n++){ flag = prime_number(n); if(flag==0){ printf("%d, ", n); } } } int prime_number(int n){ int lcv, flag; for (lcv=2; lcv <= (n / 2); lcv++) { if ((n % lcv) == 0) { return 1; } } return 0; } |
Output of the program is:
1 | Prime nmbers < 100 are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, |
