Check Whether a Number Is Prime

72.2k
0

Given an integer N, determine whether it is a Prime Number or not. Return true if it is prime, otherwise return false.

A prime number is a positive integer greater than 1 that has no positive divisors other than 1 and itself.

Example 1

Input: N = 7

Output: true

Explanation: The number 7 is divisible only by 1 and 7, so it is a prime number.

Example 2

Input: N = 12

Output: false

Explanation: The number 12 is divisible by 2, 3, 4, and 6 as well, so it is not a prime number.

Brute Force Approach

The most natural way to think about this problem is to search for an extra divisor. A prime number is only allowed to have 1 and itself as divisors, so if even one number from 2 to N - 1 divides N, the answer becomes false.

Algorithm

  • First, return false if N <= 1 because prime numbers are defined only for numbers greater than 1.

  • Start checking every integer from 2 to N - 1 because any extra divisor in this range is enough to prove that N is not prime.

  • If N % i == 0 for any checked value, return false immediately because an extra exact divisor has been found.

  • Return true after the loop finishes because no number other than 1 and N was able to divide it.

Key Points

  • 1 is not a prime number because it has only one positive divisor.

  • 0 and negative numbers are not prime.

Dry Run

Check Prime Number Brute Force Dry Run

Check Prime Number Brute Force Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/*
Checks whether the given number is prime using brute force.
*/
bool isPrime(int n) {
// Numbers less than or equal to 1 are not prime.
if (n <= 1) {
return false;
}
// Check every possible divisor from 2 to n - 1.
for (int i = 2; i < n; i++) {
// If a divisor is found, the number is not prime.
if (n % i == 0) {
return false;
}
}
return true;
}
};
// Driver code starts
int main() {
Solution sol;
int n = 29;
if (sol.isPrime(n)) {
cout << "true\n";
} else {
cout << "false\n";
}
return 0;
}

Complexity Analysis

Time Complexity: O(N), because in the worst case almost all numbers from 2 to N - 1 are checked.

Space Complexity: O(1), because only a few variables are used.

Optimal Approach

The key observation is that factors always come in pairs. If i is a factor of N, then N / i is also a factor because i × (N / i) = N. For example, for 36, the factor pairs are 2×18, 3×12, 4×9, and 6×6. After 6, the pairs simply repeat in reverse. The important point is that at least one factor in every pair must be less than or equal to √N. If both factors were greater than √N, their product would be greater than N, which is impossible. Therefore, we only need to check factors up to √N.

Instead of calculating √N, we use i * i <= N. This is exactly the same condition because i <= √N means i × i <= N. For example, when N = 36, 6 * 6 = 36, so we check 6. For i = 7, 7 * 7 = 49 > 36, meaning we have crossed √36 = 6, so we can stop. Any factor after 6, such as 9, 12, or 18, would already have its smaller partner (4, 3, or 2) checked. Thus, i * i <= N lets us find all possible factors without checking unnecessary values.

Algorithm

  • First, return false if N <= 1 because such numbers do not satisfy the definition of a prime number.

  • Return true immediately if N is 2 because it is the smallest prime number.

  • Return false immediately if N is even and greater than 2 because divisibility by 2 already proves it is not prime.

  • Start checking odd divisors from 3 because even divisors are no longer needed after the earlier even-number check.

  • Continue the loop only while i * i <= N because any divisor beyond the square root would already have a matching smaller divisor.

  • If N % i == 0 for any checked value, return false because an extra exact divisor has been found.

  • Return true after the loop finishes because no valid divisor exists other than 1 and N.

Key Points

  • Checking up to sqrt(N) is enough because factors always come in pairs.

  • 2 is the smallest prime number.

  • Every even number greater than 2 is automatically not prime.

  • The condition i * i <= N is often preferred over using an actual square root function.

Dry Run

Check Prime Number Binary Search Dry Run

Check Prime Number Binary Search Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/*
Checks whether the given number is prime or not.
*/
bool isPrime(int n) {
// Numbers less than or equal to 1 are not prime.
if (n <= 1) {
return false;
}
// 2 is the smallest prime number.
if (n == 2) {
return true;
}
// Any even number greater than 2 is not prime.
if (n % 2 == 0) {
return false;
}
// Check only odd divisors up to the square root of n.
for (int i = 3; i * i <= n; i += 2) {
// If a divisor is found, the number is not prime.
if (n % i == 0) {
return false;
}
}
return true;
}
};
// Driver code starts
int main() {
Solution sol;
int n = 29;
if (sol.isPrime(n)) {
cout << "true\n";
} else {
cout << "false\n";
}
return 0;
}

Complexity Analysis

Time Complexity: O(sqrt(N)), because only divisors up to the square root are checked, and even numbers are skipped after the initial check.

Space Complexity: O(1), because no extra data structure is needed.

FAQs

Q1. Why is 1 not a prime number?

Because a prime number must have exactly two positive divisors. The number 1 has only one positive divisor, which is 1 itself.

Q2. Why do we check only up to the square root of N?

Because if N has a divisor larger than sqrt(N), then the paired divisor must be smaller than sqrt(N). So one side of the factor pair is always enough to detect it.

Q3. Is 2 a prime number?

Yes. The number 2 has exactly two divisors, 1 and 2, so it is prime.

Q4. Are all odd numbers prime?

No. Many odd numbers are not prime. For example, 9 is odd but divisible by 3.

Q5. Can negative numbers be prime?

No. Prime numbers are defined only for positive integers greater than 1.

Q6. What is the difference between prime and composite numbers?

A prime number has exactly two positive divisors, while a composite number has more than two positive divisors.

MathsIntroduction to DSA

Read Similar Blogs

Two PointerSortingMathsBinary SearchArrays

Find the Smallest Divisor Given a Threshold

Given an integer array nums and an integer threshold , find the smallest positive integer divisor such that: After dividing every element of nums by divisor , rounding each result up, and adding al...

84.2k
Two PointerSortingMathsBinary SearchArrays

Book Allocation Problem: Allocate Minimum Pages

Given an array pages , where pages[i] represents the number of pages in the i-th book, and an integer students , allocate all books among the students. The allocation must follow these rules: Each...

63.2k
Two PointerBinary SearchGreedyMathsArrays

Aggressive Cows: Maximize the Minimum Distance

You are given an array arr of size N which denotes the position of stalls. You are also given an integer k which denotes the number of Aggressive Cows . You are given the task of assigning stalls t...

102k
Comments0