백준 1456번 거의 소수

문제

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

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

문제풀이

사용한 알고리즘 : 에라토스테네스의 체

(0) 생각

 임의의 수 X 는 root(X)보다 큰 수로 나눠지지 않습니다.

 문제에서 입력되는 수는 10^14 이하의 수이므로 10^7 이하의 소수만 찾아줄 것입니다.

 찾은 모든 소수를 거듭제곱 해보면서 A 이상 B 이하의 범위에 들어가는지 체크해줍니다.

(1) 코드 12~17

 10^7 이하의 소수를 모두 구해 저장합니다.

(2) 코드 21~29

 구해 놓은 모든 소수를 거듭제곱 해보면서 A이상 B이하의 범위에 들어가는 경우 수를 구해줍니다.

(3) 주의

 소수의 N제곱(N>=2) 입니다. 소수의 1제곱 (자기자신)은 세주면 안됩니다.

 구현을 하면서 숫자가 매우 커져서 long long 의 범위를 넘어갈 수 있습니다. 주의해주세요.

	#include<bits/stdc++.h>
	using namespace std;
	typedef long long ll;
	const int MAX = 10000001; // root(10^14) = 10^7
	ll A, B;
	bool visited[MAX];
	vector<int> Prime;
	int main() {ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	// 소수 만들어놓기
	for (int i = 2; i < MAX; ++i) {
	if (visited[i]) continue;
	Prime.push_back(i);
	for (int j = 2 * i; j < MAX; j += i) visited[j] = true;
	}
	cin >> A >> B;
	ll ans = 0LL;
	for (auto it : Prime) {
	ll curr = 1LL * it; // 현재 숫자
	ll temp = curr; // curr의 x제곱 ( 2제곱부터 답이 될 수 있다.)
	while (temp <= B / curr) { // temp*curr <= B 일때만
	temp *= curr; // 제곱해보고
	if (temp >= A) ans++; // 범위 들어오는지 체크
	}
	}
	cout << ans << '\n';
	return 0;
	}

view raw BOJ 1456.cpp hosted with ❤ by GitHub