Notice
Recent Posts
Recent Comments
Link
«   2025/06   »
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
Archives
Today
Total
관리 메뉴

PS 부수기

Project Euler #27 : Quadratic primes 본문

Project Euler

Project Euler #27 : Quadratic primes

jyheo98 2020. 8. 8. 10:57
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 = { 2761 };
llong mul(llong a, llong b, llong mod) {
    return (a * b) % mod;
}
llong bin_pow(llong a, llong p, llong mod) {
    if (p == 0return 1 % mod;
    if (p & 1return 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 - 1return true;
        d /= 2;
    }
    llong tmp = bin_pow(a, d, n);
    return tmp == n - 1 || tmp == 1;
}
bool is_prime(llong n) {
    if (n <= 1return false;
    if (n <= 10000) {
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0return 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에서 자주 쓸듯..

Comments