Practice › Basics
Prime Check
Easy · Basics · Asked at TCS, Infosys, Wipro, Accenture, Cognizant
Print YES if n is a prime number, otherwise NO.
Input
One integer n.
Output
YES or NO.
Constraints
- 1 ≤ n ≤ 10^12
Checking divisors only up to √n is fast enough. 1 is not prime.
Example 1
Input
7
Output
YES
Example 2
Input
12
Output
NO
Hints
- If n has a divisor bigger than √n, it also has one smaller than √n.
- So try divisors d while d * d ≤ n. Remember that 1 is not prime.
Approach
Divisors come in pairs (d, n/d) and one of each pair is ≤ √n. So trial division up to √n (at most 10^6 steps for n = 10^12) decides primality. Write the loop condition as d * d <= n with 64-bit integers to avoid floating-point square roots.
Complexity: O(√n) time · O(1) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
long long n;
cin >> n;
bool prime = n >= 2;
for (long long d = 2; d * d <= n; d++) {
if (n % d == 0) { prime = false; break; }
}
cout << (prime ? "YES" : "NO") << "\n";
return 0;
}Python solution
n = int(input())
prime = n >= 2
d = 2
while d * d <= n:
if n % d == 0:
prime = False
break
d += 1
print("YES" if prime else "NO")Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long n = sc.nextLong();
boolean prime = n >= 2;
for (long d = 2; d * d <= n; d++) {
if (n % d == 0) { prime = false; break; }
}
System.out.println(prime ? "YES" : "NO");
}
}