1 ~ N 까지의 Prime 중 Happy Number를 만족하는 수를 찾아서 출력해야 한다.
-1) 소수 찾기
1 ~ N 까지의 Prime을 먼저 찾아야 되므로 에라토스테네스 체를 이용한다.
#define size 1000001
bool p[size];
long long i, j;
for (i = 2; i < size; i++) {
if (p[i] == false) {
for (j = (i * i); j < size; j += i)
p[j] = true;
}
}
-2) Happy Number 찾기
숫자 N에 대해 각 자릿수의 제곱을 더해가는 과정을 반복하다,
1이 되면 Happy Number이고, 1이 나오지 않고 Cycle에 갇힌다면 Un Happy Number이다.
따라서 우리는 각 자릿수의 제곱을 더해가는 과정을 반복하며, Cycle을 체크해줘야 된다.
이때, N의 다음 happy number는 모든 자릿값이 9일 때 최대를 갖는다. 또, N이 10^6보다 작거나 같으므로
Happy Number를 구해가는 과정에서 가장 큰 값은 81 * 6인 486을 넘어갈 수 없다.
따라서, bool 배열인 c 배열을 만들어줘서, 그동안 구해온 수들을 check 해주고 같은 수가 나오면 Cycle이 생겼다고 판단하면 된다.
#include<iostream>
#include<cmath>
using namespace std;
#define size 1000001
bool p[size];
bool c[487];
int get_happynumber(int p) {
int next = 0, l;
for(l = 1; ; l++)
if ((int)pow(10, l - 1) <= p && p < (int)pow(10, l)) {
break;
}
int end = l;
for (int j = 0; j < end; j++) {
int temp = (p % (int)pow(10, l)) / (int)pow(10, l - 1);
next += temp * temp;
l--;
}
return next;
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
long long i, j;
for (i = 2; i < size; i++) {
if (p[i] == false) {
for (j = (i * i); j < size; j += i)
p[j] = true;
}
}
int n;
cin >> n;
for (int i = 2; i <= n; i++) {
int prime = i;
if (p[i] == false) {
for (int j = 0; j < 487; j++)
c[j] = false;
while (1) {
int next = get_happynumber(prime);
if (next == 1) {
cout << i << '\n';
break;
}
else if (c[next] == true) {
break;
}
else {
c[next] = true;
}
prime = next;
}
}
}
}
B의 최대 범위는 10^14 이고 , P^k( k ≥ 2 )꼴의 수는 k가 2보다 크거나 같고 10^14보다는 작거나 같으므로,
10^7 이하의 소수만 먼저 찾으면 된다. (10^7 이상의 소수는 제곱했을 때, 입력 범위를 벗어나므로 )
10^7은 배열로 선언이 가능하므로, 에라토스테네스 체를 이용해서 모든 소수를 먼저 구해야 한다.
#define size 10000001
bool p[size];
long long i, j;
for (i = 2; i < size; i++) {
if (p[i] == false) {
for (j = (i * i); j < size; j += i)
p[j] = true;
}
}
bool 배열인 p 배열에는 소수면 false, 소수가 아닌 합성수면 true가 저장됩니다.
-2) A ~ B 까지 P^k 꼴의 수를 찾기.
bool 배열인 p를 순회하며 소수를 발견하면 p * p 가 B보다 작거나 같다면, p 를 계속 곱해가며, A랑 B사이에 있는 P^k 꼴을 찾아줄 수 있다.
이때, p 를 계속 곱해나가다 p^k 꼴이 long long 범위를 벗어나는 경우가 생기므로 if 문을 통해 잡아줘야 된다.
( p 가 10^7보다는 작거나 같지만 10^7에 근접한 소수이고, B가 10^14라면 p * p 는 B보다 작거나 같으므로 while문이 실행된다. 하지만, p * p * p 인 p^3은 10^21에 근접하므로 long long 범위를 벗어나고, 오류가 발생한다.
이 문제가 정답 비율이 낮은 이유는 long long 범위를 벗어나는 경우를 못 잡아줘서 인 것 같다. )
for (i = 2; i < size; i++) {
if (i * i > B)
break;
if (p[i] == false) { // 소수를 찾았으면 소수의 k제곱꼴이 A, B사이에 몇개있는지 찾자.
long long temp = i * i;
while (temp <= B) {
if (A <= temp) {
ans++;
}
temp *= i; // temp = p^k 꼴
if (temp % i != 0) // long long 범위를 벗어나는 경우.
break;
}
}
}
-3) 최종 코드
#include<iostream>
using namespace std;
#define size 10000001
int p[size];
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
long long i, j;
for (i = 2; i < size; i++) {
if (p[i] == false) {
for (j = (i * i); j < size; j += i)
p[j] = true;
}
}
long long A, B, ans = 0;
cin >> A >> B;
for (i = 2; i < size; i++) {
if (i * i > B)
break;
if (p[i] == false) { // 소수를 찾았으면 소수의 k제곱꼴이 A, B사이에 몇개있는지 찾자.
long long temp = i * i;
while (temp <= B) {
if (A <= temp) {
ans++;
}
temp *= i;
if (temp % i != 0)
break;
}
}
}
cout << ans;
}
