PS 부수기
Project Euler #27 : Quadratic primes 본문
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
49
50
51
|
vector<llong> alist = { 2, 7, 61 };
llong mul(llong a, llong b, llong mod) {
return (a * b) % mod;
}
llong bin_pow(llong a, llong p, llong mod) {
if (p == 0) return 1 % mod;
if (p & 1) return mul(a, bin_pow(a, p - 1, mod), mod);
return bin_pow(mul(a, a, mod), p / 2, mod);
}
bool miller_rabin(llong n, llong a) {
llong d = n - 1;
while (d % 2 == 0) {
if (bin_pow(a, d, n) == n - 1) return true;
d /= 2;
}
llong tmp = bin_pow(a, d, n);
return tmp == n - 1 || tmp == 1;
}
bool is_prime(llong n) {
if (n <= 1) return false;
if (n <= 10000) {
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) return false;
}
return true;
}
for (llong a : alist) {
if (!miller_rabin(n, a)) return false;
}
return true;
}
int main() {
IOS;
int ansIndex;
int ans = 0;
for (int a = -1000; a <= 1000; a++) {
for (int b = -1000; b <= 1000; b++) {
int cnt = 0;
for (int n = 1; ; n++) {
if (is_prime(n * n + a * n + b)) cnt++;
else break;
}
if (ans < cnt) {
ansIndex = a * b;
ans = cnt;
}
}
}
cout << ansIndex;
}
|
cs |
소수 판별 알고리즘으로 miller rabin 알고리즘을 사용했다. Project euler에서 자주 쓸듯..
'Project Euler' 카테고리의 다른 글
Project Euler #29 : Distinct powers (0) | 2020.08.08 |
---|---|
Project Euler #28 : Number spiral diagonals (0) | 2020.08.08 |
Project Euler #26 Reciprocal cycles (0) | 2020.08.08 |
Project Euler #25 : 피보나치 수열에서 처음으로 1000자리가 되는 항은 몇 번째? (0) | 2020.08.07 |
Project Euler #24 : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9로 만들 수 있는 1,000,000번째 사전식 순열은? (0) | 2020.08.07 |
Comments