1.

/*
* ACM Contest training
* Problem: 11105 - Semi-prime H-numbers
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=23&problem=2046
*
* @author Christoph Goettschkes
* @version 1.0, 11/08/2010
*
* Method : Sieve of Eratosthenes
* Status : Accepted
* Runtime: 0.632
*/

import java.io.*;
import java.util.*;

class Main
{
static Set<Integer> hPrimes = new HashSet<Integer>();
static Set<Integer> semis = new HashSet<Integer>();

static int[] map = new int[1000002];

public static void main(String[] args) throws IOException {
gen(1000001);

int counter = 0;
for (int i = 1; i < 1000002; i++) {
if (semis.contains(i))
counter++;
map[i] = counter;
}

BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(reader.readLine());

while (n != 0) {
System.out.println(n + " " + map[n]);
n = Integer.parseInt(reader.readLine());
}
}

static void gen(int upperBound) {
int upperBoundSquareRoot = (int) Math.sqrt(upperBound);
BitSet isComposite = new BitSet(upperBound);

for (int m = 5; m <= upperBoundSquareRoot; m += 4)
if (!isComposite.get(m))
for (int k = m * m; k <= upperBound; k += m)
isComposite.set(k, true);

for (int m = 5; m <= upperBound; m += 4)
if (!isComposite.get(m))
hPrimes.add(m);

isComposite = new BitSet(upperBound);
for (int m = 5; m <= upperBound; m += 4)
if (hPrimes.contains(m))
isComposite.set(m, true);
else if (!isComposite.get(m))
for (long k = m * 2l; k <= upperBound; k += m)
isComposite.set((int)k, true);


for (int m = 25; m <= upperBound; m += 4)
if (!isComposite.get(m))
semis.add(m);
}
}



2.

/**
* FWP: Ausgewaehlte Probleme aus dem ACM (SS10)
*
* Method: number theory
* Problem: 11105 - Semi-prime H-numbers
* Accepted: 0.328
* @author Evgeni Pavlidis
*
*/

import java.io.*;
import java.util.*;

class Main {
private static final int MAX = 1000001;
private static int[] semiNumbers = new int[MAX+1];
private static int[] hPrimes = new int[MAX+1];
private static boolean[] isSemi = new boolean[MAX+1];
private static boolean[] isComposite = new boolean[MAX+1];
private static int hPrimesIndex = 0;

public static void main(String...args) throws Exception
{
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

int h = 5, test;
for(int i = 1; h <= MAX; i++, h = 4*i+1)
if(!isComposite[h])
{
hPrimes[hPrimesIndex++] = h;
for(int j = 0; j < hPrimesIndex && h*hPrimes[j] <= MAX; j++)
isSemi[h*hPrimes[j]] = true;

for(int j = h + h; j <= MAX; j += h)
isComposite[j] = true;
}

int counter = 0;
h = 5;
for(int i = 1; h <= MAX; i++, h = 4*i+1)
{
if(isSemi[h])
counter++;
semiNumbers[h] = counter;
}

int n;
while( (n = Integer.parseInt(reader.readLine())) != 0)
System.out.println(n + " " + semiNumbers[n]);
}
}