Algorithm to Check Whether a Number is Prime
Below is the algorithm, C program, and detailed explanation for checking whether a number is prime.
Plaintext
Step 1: Start
Step 2: Input: Read an integer n from the user.
Step 3: Process:
- If n is less than or equal to 1, it is not a prime number.
- If n is 2, it is a prime number.
- For numbers greater than 2:
- Check divisibility from 2 up to the square root of n.
- If n is divisible by any number in this range, it is not a
prime number.
- Otherwise, n is a prime number.
Step 4: Output: Display whether n is prime or not.
Step 5: EndC Program to Check Whether a Number is Prime
C
#include <stdio.h>
#include <math.h>
int main() {
int n, i, isPrime = 1; // Assume n is prime initially
// Step 2: Read an integer from the user
printf("Enter a positive integer: ");
scanf("%d", &n);
// Step 3: Check if the number is prime
if (n <= 1) {
isPrime = 0; // Numbers less than or equal to 1 are not prime
} else if (n == 2) {
isPrime = 1; // 2 is a prime number
} else if (n % 2 == 0) {
isPrime = 0; // Even numbers greater than 2 are not prime
} else {
// Check divisibility from 3 to sqrt(n)
for (i = 3; i <= sqrt(n); i += 2) {
if (n % i == 0) {
isPrime = 0; // n is divisible by i, hence not prime
break;
}
}
}
// Step 4: Output whether the number is prime or not
if (isPrime) {
printf("%d is a prime number.\n", n);
} else {
printf("%d is not a prime number.\n", n);
}
// Step 5: End
return 0;
}Explanation of Each Step
Include Headers:
C
#include <stdio.h>
#include <math.h>- The program includes standard input-output and math libraries. The math library (
math.h) is used for the sqrt function.
Main Function:
C
int main() {- The main function is the entry point of the C program.
Variable Declaration:
C
int n, i, isPrime = 1;- Three integer variables are declared: n to store the user input, i for iteration, and isPrime is initialized to 1 (true) assuming n is prime initially.
Reading Input:
C
printf("Enter a positive integer: ");
scanf("%d", &n);- printf prompts the user to enter a positive integer.
- scanf reads the integer and stores it in the variable n.
Checking Prime Status:
C
if (n <= 1) {
isPrime = 0; // Numbers less than or equal to 1 are not prime
} else if (n == 2) {
isPrime = 1; // 2 is a prime number
} else if (n % 2 == 0) {
isPrime = 0; // Even numbers greater than 2 are not prime
} else {
// Check divisibility from 3 to sqrt(n)
for (i = 3; i <= sqrt(n); i += 2) {
if (n % i == 0) {
isPrime = 0; // n is divisible by i, hence not prime
break;
}
}
}- The if-else statements determine whether n is prime:
- Suppose if n is less than or equal to 1, it is not prime (isPrime set to 0).
- If n is 2, it is prime (isPrime remains
1). - If n is even and greater than 2, it is not prime (isPrime set to 0).
- For odd numbers greater than 2, the program checks divisibility from 3 up to the square root of n(sqrt(n)).
- If n is divisible by any number in this range (i), it is not prime (isPrime set to 0).
- The loop iterates only through odd numbers (i += 2) optimize performance.
Output:
C
if (isPrime) {
printf("%d is a prime number.\n", n);
} else {
printf("%d is not a prime number.\n", n);
}- The program prints whether
nis prime or not based on the value of isPrime.
End:
C
return 0;- This line indicates successful completion of the program.
This program effectively determines whether a given integer n is prime or not using a combination of conditionals and a loop to check divisibility. It handles edge cases such as numbers less than or equal to 1, even numbers, and utilizes the square root optimization for efficient checking.
Discover more from lounge coder
Subscribe to get the latest posts sent to your email.
