// Arup Guha
// 8/26/2020
// Program to print out all Sophie Germain primes up to 1,000,000.

import java.util.*;

public class sophie {

	public static int LIMIT = 1000000;
	
	public static void main(String[] args) {
	
		// Set up prime sieve.
		boolean[] sieve = new boolean[2*(LIMIT+1)];
		Arrays.fill(sieve, true);
		sieve[0] = sieve[1] = false;
		
		// Just go to sqrt.
		for (int i=2; i*i<sieve.length; i++) {
		
			// No need to use non-primes.
			if (!sieve[i]) continue;
			
			// Mark out all numbers divisible by i.
			for (int j=2*i; j<sieve.length; j+=i)
				sieve[j] = false;
		}
		
		int cnt = 0;
		
		// Just look at odd values up to 1,000,000.
		for (int i=2; i<=LIMIT; i++) {
			if (sieve[i] && sieve[2*i+1]) {
				System.out.println(i);
				cnt++;
			}
		}
		
		// I was just curious how many of these there were!
		System.out.println("There are "+cnt+" Sophie Germain primes <= "+LIMIT);
	}
}