[BOJ] 1456 - 거의 소수

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

---

[알고리즘풀이]

A ~ B 범위에 있는 P^k 꼴의 수를 모두 Count 해주는 문제입니다.

 

-1) 소수 찾기.

B의 최대 범위는 10^14 이고 , P^k( k ≥ 2 )꼴의 수는 k가 2보다 크거나 같고 10^14보다는 작거나 같으므로,

10^7 이하의 소수만 먼저 찾으면 된다. (10^7 이상의 소수는 제곱했을 때, 입력 범위를 벗어나므로 )

10^7은 배열로 선언이 가능하므로, 에라토스테네스 체를 이용해서 모든 소수를 먼저 구해야 한다.

#define size 10000001

bool p[size];

long long i, j;
  for (i = 2; i < size; i++) {
 	 if (p[i] == false) {
 		 for (j = (i * i); j < size; j += i)
 			 p[j] = true;
	}
}

bool 배열인 p 배열에는 소수면 false, 소수가 아닌 합성수면 true가 저장됩니다.

 

-2) A ~ B 까지 P^k 꼴의 수를 찾기.

bool 배열인 p를 순회하며 소수를 발견하면 p * p 가 B보다 작거나 같다면, p 를 계속 곱해가며, A랑 B사이에 있는 P^k 꼴을 찾아줄 수 있다.

이때, p 를 계속 곱해나가다 p^k 꼴이 long long 범위를 벗어나는 경우가 생기므로 if 문을 통해 잡아줘야 된다.

( p 가 10^7보다는 작거나 같지만 10^7에 근접한 소수이고, B가 10^14라면 p * p 는 B보다 작거나 같으므로 while문이 실행된다. 하지만, p * p * p 인 p^3은 10^21에 근접하므로 long long 범위를 벗어나고, 오류가 발생한다.

이 문제가 정답 비율이 낮은 이유는 long long 범위를 벗어나는 경우를 못 잡아줘서 인 것 같다. )

	for (i = 2; i < size; i++) {
		if (i * i > B)
			break;

		if (p[i] == false) { // 소수를 찾았으면 소수의 k제곱꼴이 A, B사이에 몇개있는지 찾자.
			long long temp = i * i;
			while (temp <= B) {
				if (A <= temp) {
					ans++;
				}
				temp *= i; // temp = p^k 꼴
				if (temp % i != 0) // long long 범위를 벗어나는 경우.
					break;
			}
		}
	}

-3) 최종 코드

#include<iostream>

using namespace std;

#define size 10000001

int p[size];

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	long long i, j;
	for (i = 2; i < size; i++) {
		if (p[i] == false) {
			for (j = (i * i); j < size; j += i)
				p[j] = true;
		}
	}

	long long A, B, ans = 0;
	cin >> A >> B;

	for (i = 2; i < size; i++) {
		if (i * i > B)
			break;

		if (p[i] == false) { // 소수를 찾았으면 소수의 k제곱꼴이 A, B사이에 몇개있는지 찾자.
			long long temp = i * i;
			while (temp <= B) {
				if (A <= temp) {
					ans++;
				}
				temp *= i;
				if (temp % i != 0)
					break;
			}
		}
	}
	cout << ans;
}

---