[Gold / 1456] 거의 소수

문제 링크

---

🔷 분류

수학, 정수론, 소수 판정, 에라토스테네스의 체

✒️ 문제 설명

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

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

⬅️ 입력

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

➡️ 출력

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

💻 코드 (C++)

#include <iostream>
#include <cmath>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	long a, b;
	cin >> a >> b;
	long A[10000001];
	
	for(int i = 2; i < 10000001; i++) A[i] = i;
	for(int i = 2; i <= sqrt(10000001); i++) { // 에라토스테네스 체
		if(A[i] == 0) continue;
		for(int j = i + i; j < 10000001; j += i) A[j] = 0;
	}
	
	int ans = 0;
	
	for(int i = 2; i < 10000001; i++) {
		if(A[i] != 0) { // 소수면
			long temp = A[i];
			
			while((double)A[i] <= (double)b / (double)temp) {
				if((double)A[i] >= (double)a / (double)temp) {
					ans++;
				}
				temp *= A[i];
			}
		}
	}
	cout << ans;
	return 0;
}