[ 백준 1456 ] 거의 소수 (c/c++)

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

 

[ 문제 요약 ]

정수 A와 B 사이에 소수의 N제곱이 몇 개가 있는 지 출력한다.

 

 

[ 문제 풀이 ]

1. 우선 에라토스테네스의 체를 이용하여 소수를 구한다.

2. 소수를 가지고 범위에 속하지 않을 때까지 곱하면서 계산한다.

 

 

[ 소스 코드 ]

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

ll A, B, num, ans;
ll arr[10000001];

void Eratos() {
    for (int i=2; i<10000001; i++) arr[i] = 1;
    for (int i=2; i*i<=10000001; i++){
        if(arr[i]) {
            for (int j=i*i; j<10000001; j+=i){
                arr[j] = 0;
            }
        }
    }
}

void Find() {
    for (int i=2; i<=10000001; i++){
        if (arr[i]) num = i;
        while (num <= B / i){
            if (num * i >= A) ans++;
            num *= i;
        }
    }
    cout << ans;
}

int main() {
    cin >> A >> B;
    Eratos();
    Find();
    return 0;
}

 

 

 

[ 주의할 점 ]

범위를 계산할 때 B / i 를 해주어야 시간 초과가 걸리지 않는다.