Prime numbers are natural numbers greater than 1 that have no positive divisors other than 1 and themselves. They play a crucial role in number theory and have applications in various fields such as cryptography and Encryption and Decryption. 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 are a fundamental component of modern cryptography. The security of widely-used encryption algorithms, such as RSA, relies on the difficulty of factoring the product of two large prime numbers. This factoring process forms the basis for secure communication and data protection in various online transactions.
Understanding Cryptography: A Textbook for Students and Practitioners
C program to check for Prime Number
This program determines whether a given number is a prime number or not by checking for non-trivial factors. It iterates through the numbers from 2 to half of the input number and prints the non-trivial factors if found. If no factors are found, it declares the number as prime.
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 29 30 31 32 | #include <stdio.h> int main(void) { int n, lcv, flag; // Prompt the user to enter a value for N printf("Enter value of N > "); scanf("%d", &n); // Initialize the flag to indicate whether non-trivial factors are found for (lcv = 2, flag = 1; lcv <= (n / 2); lcv++) { // Check for non-trivial factors if ((n % lcv) == 0) { if (flag) { // Print the header if it is the first non-trivial factor printf("The non-trivial factors of %d are: \n", n); } // Reset the flag and print the non-trivial factor flag = 0; printf(" %d, ", lcv); } } // Check the flag to determine if the number is prime if (flag) { printf("%d is prime\n", n); } // Add a new line for better formatting printf("\n"); return 0; // Indicate successful execution } |
Output of the program is the following if user enters a non prime number:
1 2 3 | Enter value of N > 36 The non-trivial factors of 36 are: 2, 3, 4, 6, 9, 12, 18, |
And the output of the program is the following if user enters a prime number:
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. This version of the C program uses a separate function (is_prime) to check for prime numbers. The main function takes user input, calls the is_prime function to determine primality, and then prints the result. The code is organized with clearer comments, better function naming, and improved formatting.
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 29 30 31 32 33 34 35 36 37 38 39 | #include <stdio.h> // Function prototype int is_prime(int); int main(void) { int n, flag; // Prompt the user to enter a value for N printf("Enter value of N > "); scanf("%d", &n); // Call the function to check if the number is prime flag = is_prime(n); // Print the result based on the flag if (flag == 0) { printf("%d is prime\n", n); } else { printf("%d is NOT prime\n", n); } return 0; } // Function to check if a number is prime int is_prime(int n) { int lcv; for (lcv = 2; lcv <= (n / 2); lcv++) { // If the number is divisible by lcv, it is not prime if ((n % lcv) == 0) { return 1; } } return 0; } |
Output of the program is the following if user enters a non prime number:
1 2 | Enter value of N > 25 25 is NOT prime |
And the output of the program is the following if user enters a prime number:
1 2 | Enter value of N > 19 19 is prime |
C Program to Print all Prime Numbers under 100
We can further modify the above program to print all of the primer numbers in the range of 2-100. This program generates prime numbers less than 100. It utilizes a loop to iterate through numbers from 2 to 100, calling the is_prime function to check for primality. Prime numbers are then printed, providing a list of prime numbers below 100. The program showcases how prime numbers can be systematically identified within a specific range.
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 29 30 31 32 33 34 35 36 37 38 39 | #include <stdio.h> // Function prototype int is_prime(int); int main(void) { int n, flag; // Print the header printf("Prime numbers < 100 are: "); // Loop through numbers from 2 to 100 for (n = 2; n <= 100; n++) { // Check if the number is prime using the function flag = is_prime(n); // Print the prime number if (flag == 0) { printf("%d, ", n); } } return 0; } // Function to check if a number is prime int is_prime(int n) { int lcv; // Loop through potential factors for (lcv = 2; lcv <= (n / 2); lcv++) { // If the number is divisible by lcv, it is not prime if ((n % lcv) == 0) { return 1; } } return 0; } |
Output of the C program is:
1 | Prime numbers < 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, |
Frequently Asked Questions about Prime Numbers
How many prime numbers are there in between 1 to 1000?
There are a total of 168 prime numbers in between 1 to 1000 as listed below:
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, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997
Why are prime numbers important in mathematics?
Prime numbers are fundamental in number theory and have applications in cryptography, coding theory, and various mathematical algorithms.
How are prime numbers used in cryptography?
Prime numbers form the basis of many cryptographic algorithms, such as RSA. The security of these algorithms relies on the difficulty of factoring the product of two large prime numbers.
What is the Sieve of Eratosthenes?
The Sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to a given limit. It works by iteratively marking the multiples of each prime, gradually eliminating non-prime numbers.
How do computers efficiently generate large prime numbers?
Computers often use probabilistic algorithms, like the Miller–Rabin primality test, to quickly determine if a number is likely to be prime. These algorithms provide high certainty while being computationally efficient.
