[백준 1456] 거의 소수 (C++)

https://www.acmicpc.net/problem/1456

문제

---

어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다.

두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다.

 

입력

---

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

 

출력

---

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

 

제한

---

• 1 ≤ A ≤ B ≤ 10¹⁴

 

문제 풀이

---

에라토스테네스의 체를 활용한 문제.

 

sqrt(B)를 초과하는 수에 대해서는 2제곱의 값이 B를 넘어가므로 거의 소수가 존재하지 않는다. 따라서 sqrt(B)까지의 소수들을 에라토스테네스의 체를 이용해 구해 벡터에 저장한다.

모든 소수들을 구했다면 벡터의 각 원소(=소수)들에 대해 A와 B 사이에 있는 거의 소수들의 개수를 구해주면 된다. 소수 p에 대해 어떤 수 X까지의 거의 소수의 개수는 log_pX에서 p를 제외해야 하므로 1을 뺀 값이 된다.

X까지의 p의 제곱의 개수를 구하려면 p에서 시작해 X보다 작거나 같은 동안 p를 계속 곱해 몇 제곱까지 나올 수 있는지 구할 수 있으나, 이 문제의 제한은 10¹⁴ 까지이므로 long long의 범위를 벗어난다. 따라서 반대로 X가 p보다 작을 때까지 X에서 계속 p를 나누어 몇 번 나눌 수 있는지 구한다.

 

소수 p에 대해 B까지의 거의 소수들을 구하고, A-1까지의 거의 소수들을 구해 두 값을 빼주면 p에 대한 A~B 범위의 거의 소수들의 개수를 구할 수 있다.

 

아래는 코드.

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
bool* isPrime;
vector<long long> primes;
long long A, B;

int getAlmostPrimeCount(long long B, long long prime)
{
	long long N = B;
	int count = 0;
	while (N >= prime)
	{
		N /= prime;
		count++;
	}
	return max(0, count - 1);
}

void getPrimes()
{
	for (long long i = 0; i <= sqrt(B); i++)
	{
		isPrime[i] = true;
	}
	isPrime[0] = false;
	isPrime[1] = false;
	for (long long i = 2; i <= sqrt(B); i++)
	{
		for (long long j = 2 * i; j <= sqrt(B); j += i)
		{
			isPrime[j] = false;
		}
	}
	for (long long i = 2; i <= sqrt(B); i++)
	{
		if (isPrime[i] == true)
		{
			primes.push_back(i);
		}
	}
}

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

	long long answer = 0;
	cin >> A >> B;
	isPrime = new bool[10000001];

	getPrimes();
	for (long long i = 0; i < primes.size(); i++)
	{
		int countToB = getAlmostPrimeCount(B, primes.at(i));
		int countToA = getAlmostPrimeCount(A-1, primes.at(i));
		answer += countToB - countToA;
	}
	cout << answer << "\n";
	return 0;
}