문제 접근법:
이 문제를 어떻게 접근했냐면
우선 에라토스테네스의 체를 이용하여 모든 소수를 10^7 까지 구하면됩니다.
p를 소수라 했을때 p^n<10^14 이니 이때(n>=2)라고 문제에 적혀있고 n에 2만 넣고 두 식에 제곱근을 넣어주면
p<10^7 꼴이 되버리니 p가 가질수있는 최대값은 10^7보다는 작은수중 10^7에 가장까까운 소수중 하나겠죠
그리고 벡터를이용해 모든 소수를 넣어 2,3,5 7,11 13 17 ~~~ 이 소수들을 넣게된다면 이 수들은 자연스럽게 정렬이
되어있습니다. 그렇기에 a<=b라는걸 문제에 나와있으니 b의 제곱근 즉 sqrt(b)를 구하여 lower_bound를 이용하여
b의 제곱근 혹은 b의 제곱근보다 조금 큰 소수를 찾아 범위를 2~lower_bound(b)까지 거의 소수를 찾기만 하면 되는문제로 생각하여 문제를 풀었습니다.
또한 이문제는 거의 소수를 구하기위해
p^n을 하다보니 자료의 범위를 초과해버려서 그것을 막아야하는데
p^n<=b까지만 구하는거니(n>=2)
잘생각해보면
n은 2라고 생각하면,
p<=b/p 도 성립하고
n은 3일때도
p<=b/p^2도 성립하니
p<=b/p^(n-1)이 성린한다는 얘기고
p>b/p^(x)일때는 p를 x번 곱했을때 거의소수가 아니라는것으 알기때문에 굳이 곱할필요없다는것을 알수있습니다.
그럼 코드를 확인 해보시면
|
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
44
45
46
47
48
|
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
char p[15000001];//소수를 위한 배열
vector<long long> v;//이안에 소수만 담는 백터를 담아줌
long long a, b;
void erathos(){
p[0] = 1;
p[1] = 1;
for (int i = 2; i <= (1e+7) + 5 * (1e+6); i++)//실제로 1000만까지만 해줘도되지만 넉넉하게
{
if (p[i] == false){
v.push_back(i);
for (int j = i * 2; j <= (1e+7) + 5 * (1e+6); j += i){
p[j] = true;
}
}
}
}
int main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
erathos();
cin >> a >> b;
int cnt = 0;
long long sqrtb = sqrt(b);
auto first = v.begin();//이분탐색으로 현재 첫번째 인덱스를 찾음
auto last = lower_bound(v.begin(), v.end(), sqrtb);// 그에 해당하는 인덱스만 찾고 sqrt는 어차피 제곱이상을 구하는거니 제곱근이하까지만 구하면됨
for (auto it = first; it <= last; it++){//첫번째부터 last까지만
unsigned long long sqr = *it;
for (long long j = 2;; j++){
if (*it > (b / sqr))//자료형 초과를 막기위해서
break;
sqr *= *it;
if ((a <= sqr&&sqr <= b))//이범위안에 들어간다면 cnt값을 증가
cnt++;
}
}
cout << cnt << "\n";
}
|
cs |
이렇게 이분탐색도 이용해보는것도 좋겠죠?
질문사항은 댓글을 달아주세요 ㅎㅎ 성의껏 답변드리겠습니다.
'백준' 카테고리의 다른 글
| 백준 1890 점프 (0) | 2020.07.22 |
|---|---|
| 백준 17830 이진수씨의 하루 일과 (0) | 2020.07.22 |
| 백준 2630 색종이 만들기 (0) | 2020.07.20 |
| 백준 5427 불 (0) | 2020.07.20 |
| 백준 1992 쿼드트리 (0) | 2020.07.20 |
