[백준1456] 거의 소수

입력

첫째 줄에 왼쪽 범위 A와 오른쪽 범위 B가 공백 한 칸을 사이에 두고 주어진다.

출력

첫째 줄에 총 몇 개가 있는지 출력한다.

제한

1 ≤ A ≤ B ≤ 10e14

에라스토네의 체를 이용하여 소수를 먼저구하고
그 소수들의 n제곱값이 입력된 a와 b사이에 판단하는 문제입니다.

long long arr[10000003] = { 0, };

먼저 배열선언은 10의 7승으로 해줍니다.
이유는 위에서 제한이 1 ≤ A ≤ B ≤ 10e14
이지만 에라스토네의 체는 제곱근까지만 보기 때문에 선언을
10e7로 선언하여줍니다.

for (long long i = 2; i < 10000001; i++)
	{
		arr[i] = i;
	}

	for (long long i = 2; i <= sqrt(10000001); i++)
	{
		if (arr[i] == 0)
			continue;

		for (long long j = i + i; j < 10000001; j += i)
		{
			arr[j] = 0;
		}

	}

다음은 소수를 구는 부분입니다 .에라스토네의 체와 똑같습니다 .
문제에서 요구한 10e7까지 소수를 구하여 줍니다.

	for (long long i = 2; i < 10000001; i++)
	{
		if (arr[i] != 0)
		{
			long long tmep = i;
			while ((double)arr[i]<= (double)m/ (double)tmep)
			{
				if ((double)arr[i] >= (double)n / (double)tmep)
				{
					cnt++;
				}
				tmep *= arr[i];
				
			}
		}
	}

다음은 제곱을 판단하는 로직입니다.
각각의 소수에 관해 소수를 n제곱한 값이 b(m)보다 커질 때까지 반복분을 실행합니다.
이때 소수를 n제곱한 값이 a보다 크거나 같으면 거의 소수로 판단해
카운트 합니다.

이부분을 n의k승과 b값으로 표현하면 도중 값이 변수 표현 범위를 초과하는 경우가 발생합니다.
따라서 n과b/n룰 비교하는 식으로 정리해야 합니다.

느낀점 :
값이 크면 long을 써야하는지 잘 봐야한다.