Twin Primes up to N
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
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.
/*
* 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)
- Which loop limit keeps p + 2 inside the range?