public class SiebDesEratosthenes
{
	public static int[] Sieb(int n)
	{
		boolean gestrichen[] = new boolean[n+1];
		int result[]         = new int[n+1];
		int ptr              = 0;

		for (int i = 2; i <= n; i++)
		{
			gestrichen[i] = false;
		}

		for (int i = 2; i <= n; i++)
		{
			if (!gestrichen[i])
			{
				result[ptr] = i;
				ptr         = ptr+1;

				for (int j = i*i; j <= n; j = j+i)
				{
					gestrichen[j] = true;
				}
			}
		}

		return result;
	}

	public static double Anzahl(int[] sieb)
	{
		int anzahl = 0;

		for (int i = 0; i < sieb.length; i++)
		{
			if (sieb[i] != 0) anzahl++;
		}

		return anzahl;
	}

	public static double Dichte(int[] sieb)
	{
		return Anzahl(sieb) / (sieb.length-1);
	}

	public static void main(String[] args)
	{
		for (int i = 1; i <= 100; i++)
		{
			System.out.println("Pi(" + i + "): " + (int)Anzahl(Sieb(i)));
		}

		for (int i = 1; i <= 100; i++)
		{
			System.out.println("Pi(" + i +") / " + i + ": " + Dichte(Sieb(i)));
		}
	}
}