Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. If n has a divisor bigger than √n, it also has one smaller than √n.
  2. 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");
    }
}

Solve Prime Check online · All practice problems