범위가 10^14이다. 다행히 N제곱 꼴인 경우를 물어봤으므로, 10^7까지의 소수를 미리 구해놓고, 2제곱/3제곱/...을 잘 세어보면 된다.
코드의 생명은 오버플로우 관리. 예를 들어서, 소수 p를 곱해가면서 b보다 커질 때까지 한다고 하면, b가 10^14라고 하면 10^7보다 약간 작은 소수에 대해서는 10^21 정도까지 가게 되는데, 이는 long long 범위도 넘어선다. 적당히 max값을 잡는 것이 이롭다.
#include <iostream>
#define N 10000005
using namespace std;
bool notprime[N];
int main() {
for (int i = 2; i * i < N; ++i) {
if (!notprime[i]) {
for (int j = i * 2; j < N; j += i) notprime[j] = 1;
}
}
long long a, b;
cin >> a >> b;
int ans = 0, maxp = 100;
for (long long i = 2; i < N; ++i) {
if (notprime[i]) continue;
long long now = i * i;
int p = 2;
while (p <= maxp && now <= b) {
if (now >= a) ans++;
now *= i;
p++;
}
maxp = p - 1;
if (maxp == 1) break;
}
cout << ans;
}
백준 5641번: 분명한 쌍둥이 소수
흥미로운 문제. p와 p + 2가 모두 소수일 때, (p, p + 2)를 쌍둥이 소수라고 하는 것은 다들 잘 알 것이다.
문제는 3500~5000 자리의 쌍둥이 소수를 아무거나 출력하라는 것. 이 문제는 사실 못 푸는 문제다.
다행히도, 문제에서 쌍둥이 소수 말고 분명한 쌍둥이 소수를 쓰라고 하는데, 이는 주어진 t 이하의 수로만 나누어 떨어지지 않으면 된다.
가장 쉬운 방법은, t 이하의 모든 소수를 곱한다음에 $\pm1$을 해주면, 어떤 수로도 나누어떨어지지 않는다.
t 이하의 모든 소수를 곱하면 3421자리의 수가 나온다. 3500자리라는 뜬금없는 길이가 왜 나왔는지 깨달을 수 있는 부분이다.
1을 빼고, 9를 적당히 붙여주면 완성이다.
큰 수의 곱이 나오므로 python으로 풀었다.
prime = [1 for i in range(8001)]
prime[0] = prime[1] = 0
i = 2
while i * i <= 8000:
if prime[i]:
j = i * i
while j <= 8000:
prime[j] = 0
j += i
i += 1
ans = 1
for i in range(8001):
if prime[i]:
ans *= i
while True:
n, t = input().split()
if n == '0':
break
print(ans - 1, end = '')
for i in range(int(n) - 3421):
print('9', end = '')
print()
연속하는 합성수의 길이 중 가장 긴 것이 얼마인지 문득 궁금해졌다. int범위에서만 돌려본 결과, 1453168142~1453168432까지 291짜리 합성수 sequence가 가장 길다.
#include <iostream>
using namespace std;
bool isPrime(unsigned int n) {
if (n < 2) return 0;
if (n % 2 == 0) {
if (n == 2) return 1;
else return 0;
}
int s = __builtin_ctz(n - 1);
for (unsigned long long a: {2, 7, 61}) {
if (a >= n) continue;
int d = (n - 1) >> s;
unsigned long long now = 1;
while (d != 0) {
if (d & 1) now = (now * a) % n;
a = (a * a) % n;
d >>= 1;
}
if (now == 1) goto success;
for (int i = 0; i < s; ++i) {
if (now == n - 1) goto success;
now = (now * now) % n;
}
return 0;
success:;
}
return 1;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int tc;
cin >> tc;
unsigned int n;
while (tc--) {
cin >> n;
while (!isPrime(n++));
cout << n - 1 << '\n';
}
}
백준 9176번: 메르센 합성수
2^p -1 (p는 소수) 꼴은 보통 소수인데, 이를 메르센 소수라고 한다. 합성수이면 메르센 합성수라고 부른다. 이를 출력하는 문제.
사실 이 문제는 2^61 - 1이 메르센 소수인데, 이를 테스트하는 데에 시간을 거의 잡아먹는다.
이렇게 n이 한정되어 있고, 시간초과가 간당간당해보이는 문제는 전형적인 해결책이 있는데, 바로 로컬 컴퓨터에서 돌린 다음에 그 결과를 코드에 그냥 집어넣는 것.
n이 80 정도면 이렇게 작성해야만 풀 수 있을 것 같다. 나는 그냥 61 이하만 테스트하는 식으로 작성하였다.
#include <iostream>
#include <vector>
using namespace std;
bool isPrime(int n) {
for (int i = 2; i * i <= n; ++i) {
if (n % i == 0) return 0;
}
return 1;
}
int main() {
int n;
scanf("%d", &n);
for (int i = 7; i <= min(n, 59); ++i) {
vector<long long> res;
if (isPrime(i)) {
long long t = (1LL << i) - 1;
for (long long j = 3; j * j <= t; j += 2) {
if (t % j == 0) {
t /= j;
res.push_back(j);
}
}
res.push_back(t);
}
if (res.size() > 1) {
for (int i = 0; i < res.size(); ++i) {
if (i != 0) printf(" * ");
printf("%lld", res[i]);
}
printf(" = %lld", (1LL << i) - 1);
printf(" = ( 2 ^ %d ) - 1\n", i);
}
}
}
백준 4233번: 가짜소수
페르마의 소정리를 만족하지만, 실제로는 소수가 아닌 쌍을 출력하는 문제이다.
소수 판별을 먼저 하고, 그 다음 주어진 식을 판별해야 한다.
유의할 점은 $a^p \equiv a (\text{mod} p)$와 $a^{p-1} \equiv 1 (\text{mod} p)$가 같지 않다는 점. p가 소수일 때는 같지만, 이 문제에서는 p가 소수가 아닐 수 있기 때문이다. 괜히 이상하게 했다 틀렸습니다만 하나 추가되었다...
#include <iostream>
using namespace std;
bool isPrime(unsigned int n) {
if (n < 2) return 0;
if (n % 2 == 0) {
if (n == 2) return 1;
else return 0;
}
int s = __builtin_ctz(n - 1);
for (unsigned long long a: {2, 7, 61}) {
if (a >= n) continue;
int d = (n - 1) >> s;
unsigned long long now = 1;
while (d != 0) {
if (d & 1) now = (now * a) % n;
a = (a * a) % n;
d >>= 1;
}
if (now == 1) goto success;
for (int i = 0; i < s; ++i) {
if (now == n - 1) goto success;
now = (now * now) % n;
}
return 0;
success:;
}
return 1;
}
int power(int base, int index, int mod) {
long long ret = 1;
while (index != 0) {
if (index & 1) ret = (ret * base) % mod;
base = ((long long)base * base) % mod;
index >>= 1;
}
return ret;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int p, a;
while (cin >> p >> a, p || a) {
if (!isPrime(p) && power(a, p, p) == a) cout << "yes\n";
else cout << "no\n";
}
}
