반응형
https://www.acmicpc.net/problem/1456
1456번: 거의 소수
어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다. 두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다.
www.acmicpc.net
1. arr 배열을 만들어 각 소수 여부를 저장합니다.
2. 소수를 vector<ll> prime에 저장합니다.
3. for문을 통해 prime을 돌면서 거듭제곱을 해주고, 그 수가 A <= N <= B 라면 ans++를 해줍니다. 이때, 오버플로우가 날 수도 있어서 해당 값을 i로 나눈 나머지가 0일 때 조건을 추가해 줍니다.
4. ans를 출력합니다.
[ 소스코드 ]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 | #include<iostream> #include<vector> #define ll long long using namespace std; ll A, B; int arr[10000001]; vector<ll> prime; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> A >> B; for (ll i = 2; i * i <=B; i++) { if (!arr[i]) { prime.push_back(i); for (int j = 2; i * j * i * j <= B; j++) { arr[i * j] = 1; } } } int ans = 0; for (ll i : prime) { if (!arr[i]) { ll temp = 1LL * i; while(1){ temp *= 1LL * i; if (temp > B || temp % i != 0) break; if (temp < A) continue; ans++; } } } cout << ans; } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 17298번 - 오큰수 (C++) (0) | 2023.07.08 |
|---|---|
| [ 백준 ] 6198번 - 옥상 정원 꾸미기 (C++) (0) | 2023.07.07 |
| [ 백준 ] 1038번 - 감소하는 수 (C++) (0) | 2023.07.05 |
| [ 백준 ] 11402번 - 이항 계수 4 (C++) (0) | 2023.07.04 |
| [ 백준 ] 11401번 - 이항 계수 3 (C++) (0) | 2023.07.02 |