105 views
Prime Number in C++
To determine whether a given number is prime in C++, you can use a simple algorithm that checks if the number is divisible by any integers from 2 to the square root of the number. If it’s not divisible by any of these integers, it’s a prime number. Here’s a C++ program to check for prime numbers:
C++
#include <iostream>
#include <cmath>
bool isPrime(int number) {
if (number <= 1) {
return false; // 0 and 1 are not prime
}
if (number <= 3) {
return true; // 2 and 3 are prime
}
if (number % 2 == 0 || number % 3 == 0) {
return false; // Numbers divisible by 2 or 3 are not prime
}
// Check for prime by testing divisors from 5 to the square root of the number
for (int i = 5; i * i <= number; i += 6) {
if (number % i == 0 || number % (i + 2) == 0) {
return false; // Number is divisible by i or i+2, so it's not prime
}
}
return true; // If no divisors were found, the number is prime
}
int main() {
int n;
std::cout << "Enter a number: ";
std::cin >> n;
if (isPrime(n)) {
std::cout << n << " is a prime number." << std::endl;
} else {
std::cout << n << " is not a prime number." << std::endl;
}
return 0;
}In this program:
- We first handle special cases: 0 and 1 are not prime, and 2 and 3 are prime.
- We use a loop to check for divisibility starting from 5 up to the square root of the number. We increment
iby 6 in each iteration because we have already checked divisibility by 2 and 3, so we only need to consider numbers of the form 6k ± 1. - Within the loop, we check if the number is divisible by
iori + 2. If it is, we returnfalsebecause it’s not prime. - If none of the divisors were found, the number is considered prime, and we return
true.
This program allows you to input a number, and it will tell you whether that number is prime or not.