Twin Primes up to N

medium Number Problems

Problem

Twin primes are two primes that differ by 2. Read an integer n and print every pair (p, p + 2) where both numbers are prime and p + 2 is not larger than n. Print one pair per line in ascending order. Print nothing if there is no pair.

Constraints

  • 0 <= n <= 10^5

Examples

Input

30

Output

3 5
5 7
11 13
17 19

Solutions

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

For each p we test p and p + 2 with the prime check. The loop stops early enough so that p + 2 does not go over the limit.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : List all twin prime pairs up to n.
 * Input   : One integer n.
 * Output  : One pair per line: the two primes separated by a space.
 * Approach: Test p and p + 2 with a prime check.
 * Time    : O(n * 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(int number) {
        if (number < 2) {
            return false;
        }
        for (int divisor = 2; divisor * divisor <= number; divisor++) {
            if (number % divisor == 0) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        int limit = new Scanner(System.in).nextInt();

        // Step 1: Let p go from 2 up to limit - 2, so that p + 2 is never larger than the limit.
        for (int p = 2; p + 2 <= limit; p++) {
            // Step 2: Print the pair if p and p + 2 are both prime.
            if (isPrime(p) && isPrime(p + 2)) {
                System.out.println(p + " " + (p + 2));
            }
        }
    }
}
Hints (1)
  1. Which loop limit keeps p + 2 inside the range?