[1456] 거의 소수 - C++

---

1. 문제의 추상화

A ~ B (A, B포함) 사이의 수 중에서 거의 소수를 구한다.

거의 소수란 소수를 N제곱한 수를 말한다.

 

예를 들면 $5^2 = 25$,    $5^3 =  125$,    $7^2 = 49$ 등이 문제에서 말하는 "거의 소수"이다.

 

---

2. 문제 계획

에라토스테네스의 체를 사용하여 소수들을 찾아낸다.

소수들의 집합을 순회하며 "거의 소수"를 찾아낸다.

 

위처럼 크게 두 가지로 나눌 수 있다.

---

3. 주의해야 할 점

$10^{14}$은 100조이다.

여기서 우리는 INTOVERFLOW를 조심해야 함을 알 수 있다.

 

---

4. 에라토스 테네스

const int Max = 10'000'000; //10^7 : 1000만
vector<bool> arr(Max+1, 1);
void decimal(){
  for(int i = 2; i * i<= Max; ++i){
    if(!arr[i]) continue;
    for(int j = i*i; j <= Max; j += i) arr[j] = 0;
  }
}

Max를 왜 1000만으로 놨을지 궁금할 수 있다.

 

$(10^7)^2 = 10^{14}$ 이기 때문에 $10^7$을 초과하는 소수는 범위에 맞는 거의 소수가 나올 수 없다!

그렇기에 우리는 에라토스테네스의 체를 통해 $10^7$승 이하의 소수를 모두 찾으면서 문제풀이를 시작한다.

 

---

5. 거의 소수 찾기

typedef unsigned long long int uli;

uli result = 0, a, b;

int main(){
  decimal();
  arr[0] = 0, arr[1] = 0;
  cin >> a >> b;
  for(uli i = 2; i <= Max; ++i){
    uli cnt = i;
    if(!arr[i])continue;
    while(cnt <= b/i){
      result += (cnt * i >= a);
      cnt *= i;
    }
  }
  cout << result;
  return 0;
}

INTOVERFLOW를 최대한 방지하기 위해 모두 unsigned long long int로 선언했다.

 

소수가 Check 되어있는 배열을 돌면서 거의 소수를 구하게 된다.

그런데 while 조건 부분의$\frac {b}{i}$ 부분이 이해가 안 될 거라 생각된다.

 

위 코드에서

$cnt$는 거의 소수를 말하고

$i$는 소수를 말한다.

 

$$cnt \leq \frac {b}{i}$$

$$cnt \times i \leq b$$

 

왜 필요한 걸까?

 

$10^7$이 소수는 아니지만 이걸로 예를 들어보자.

$(10^7)^2$은 $10^{14}$라 INTOVERFLOW가 될 일은 없지만

$(10^7)^3$은 $10^{21}$라 INTOVERFLOW가 된다.

 

이걸 방지하기 위한 것이다.

 

아직 이해가 되지 않는 다면 코드를 아래처럼 바꾼 후,

$i = 10^7, cnt = 10^7, b = 10^{14}, a = 1$로 두고 따라가 보도록 하자

while(cnt*i <= b){
      result += (cnt * i >= a);
      cnt *= i;
    }

---

6. 문제를 풀어보며

$cnt \leq \frac {b}{i}$ 와 $cnt \times i \leq b$ 이 둘은 큰 차이가 있다.

이렇게 자그마한 차이로 INTOVERFLOW를 만날 수도, 만나지 않을 수도 있음을 알았다.