<백준> 1456

거의 소수

문제
어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다.
두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다.

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

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	long long a, b;
	cin >> a >> b;

	long long arr[10000001];

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

	for (int i = 2; i <= sqrt(10000001); i++)
	{
		if (arr[i] == 0)
			continue;
		for (int j = i * i; j < 10000001; j += i)
		{
			arr[j] = 0;
		}
	}

	int count = 0;

	for (int i = 2; i < 10000001; i++)
	{
		if (arr[i] != 0)
		{
			long long temp = arr[i];

			while ((double)arr[i] <= (double)b / (double)temp)
			{
				if ((double)arr[i] >= (double)a / (double)temp)
					count++;
				temp = temp * arr[i];
			}
		}
	}
	cout << count;
}