public static void main(String[] args) {
//		int threads = 10;
//		for (int i = 0; i < threads; i++) {
//			new Problem216((TARGET/threads)*(i+1), (TARGET/threads)*i, ""+i);
//		}

		int limit = 1000000;
		Set<Long> set = new HashSet<Long>();
		for (long i = 2; i <= limit; ++i) {
			set.add(i);
		}
		
		int ant = 0;
		int i = 0;
		for (Integer prime : Euler.primeList(2*limit)) {
			if (++i % 10 == 0)
				System.out.println(prime + " " + set.size());
			if (prime != 2) {
				Set<Long> remove = new HashSet<Long>();
				for (Long integer : set) {
					if (prime > 2*integer) {
						remove.add(integer);
						++ant;
					} else if ((2*integer*integer-1)%prime == 0) {
						remove.add(integer);
					}
				}
				set.removeAll(remove);
			}
		}
		System.out.println(ant);
	}