[백준 / BOJ] C++ 1456 거의 소수

1456번: 거의 소수

 

문제

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

1456번: 거의 소수

 

 

풀이

거의 소수는 소수의 N제곱 형태인 수를 말한다. 범위 내 거의 소수의 개수를 구하는 문제다.

 

수의 범위가 10^14이고 N제곱 형태를 구하므로 에라토스테네스의 체를 사용해 10^7까지의 소수만 구해준다. 소수를 i라고 한다면 i^2 = i × i부터 범위에 포함된다면 카운트를 증가시켜 주면 된다.

 

단, 범위 판단에 주의해야한다. 현재 수의 +1승이 범위 내인지 확인하려면 (현재수 × i)가 B보다 작아야 한다. 하지만 곱셈은 N제곱하다 보면 long long 범위에 벗어나 overflow가 날 수 있기 때문에 (현재수가 B ÷ i보다 작을 때)로 기준을 잡아줘야 한다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  vector<int> sieve(10000001, 1), prime;
  for (int i = 2; i <= 10000000; i++)
    if (sieve[i]) {
      prime.push_back(i);
      for (int j = i * 2; j <= 10000000; j += i)
        sieve[j] = 0;
    }
  long long a, b, ans = 0;
  cin >> a >> b;
  for (int i : prime) {
    long long tmp = i;
    while (tmp <= b / i) {
      tmp *= i;
      if (tmp >= a)
        ans++;
    }
  }
  cout << ans << '\n';
  return 0;
}