#include <stdio.h>

#define MAX 100000
#define K    10000

int main()
{	
	int rads[MAX], factor, i;

	/* Filling array with 1s */
		for (i = 0; i < MAX; i++)
	{
		rads[i] = 1;
	}	
	/* Element rads[i] will represent the radical of number i+1 */

	/* Creating radicals */
	/* It works on the idea that any number with prime factor P is also a multiple of P. Also, any number that still equals 1 by the time the factor FOR loop gets to it must be a prime number, because if it had any factors other than itself it would be multiplied by them already. */
	
	for (factor = 2; factor <= MAX; factor++)
	{
		if (rads[(factor-1)] == 1)
		{
			for (i = (factor-1); i < MAX; i=i+factor)
			{
				rads[i] = (factor * rads[i]);
			}
		}
	}

	/* Sort-of sorting */
	
	int almostE[K], a, b, x;
	b = 0;
	
	for (x = 0; b < K ; x++)
	{
		for (a = 0; (a < MAX) && (b < K); a++)
		{
			if (rads[a] == x)
			{
				almostE[b] = (a+1);
				b++;
			}
		}
	}
	
	printf("Answer: %d\n", almostE[K-1]);
}