Twin Prime Check

medium Number Problems

Problem

Twin primes are two prime numbers that differ by 2, such as 11 and 13. Read an integer n and print true if n and n + 2 are both prime, otherwise false.

Constraints

  • 0 <= n <= 10^12

Examples

Input

11

Output

true

Input

7

Output

false

Solutions

Best approachTime O(sqrt(n))Space O(1)

We write a small helper that checks a prime number with the square root limit. Then we call the helper twice and combine both answers with AND.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Check if n and n + 2 are both prime.
 * Input   : One integer.
 * Output  : true or false.
 * Approach: Test two numbers with a prime check.
 * Time    : O(sqrt(n))
 * Space   : O(1)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    // This method receives a number and returns true if it is a prime number.
    static boolean isPrime(long value) {
        if (value < 2) {
            return false;
        }
        for (long divisor = 2; divisor * divisor <= value; divisor++) {
            if (value % divisor == 0) {
                return false;
            }
        }
        return true;
    }

    // This method receives a number and returns true if n and n + 2 are both prime numbers (twin primes).
    static boolean isTwinPrime(long number) {
        // Step 1: The number n and the number n + 2 must both be prime.
        // Step 2: We use the && operator. It is true only if both sides are true.
        return isPrime(number) && isPrime(number + 2);
    }

    public static void main(String[] args) {
        long number = new Scanner(System.in).nextLong();
        System.out.println(isTwinPrime(number));
    }
}
Hints (2)
  1. Write a method that checks one prime.
  2. Call it for n and for n + 2.