Kiểm tra số Pythagorean Prime C++

Pythagorean Prime – Số nguyên tố dạng 4n + 1 (theo định lý Fermat về tổng 2 bình phương).

Đặc trưng: Số nguyên tố p là Pythagorean Prime ⇔ p % 4 == 1 (trừ p=2).

Chương trình C++

#include <bits/stdc++.h>
using namespace std;

bool isPrime(int n) {
    if (n < 2) return false;
    if (n % 2 == 0) return n == 2;
    for (int i = 3; i*i <= n; i += 2)
        if (n % i == 0) return false;
    return true;
}

bool isPythagoreanPrime(int n) {
    return isPrime(n) && (n % 4 == 1);
}

int main() {
    vector test = {5, 13, 17, 29, 37, 41, 53, 2, 3, 7, 11, 19};
    for (int n : test)
        cout << n << ": " << (isPythagoreanPrime(n) ? "Pythagorean Prime" : "Khong") << "\n";
    return 0;
}

Kết quả

5: Pythagorean Prime (1^2+2^2)
13: Pythagorean Prime (2^2+3^2)
17: Pythagorean Prime (1^2+4^2)
29: Pythagorean Prime (2^2+5^2)
37: Pythagorean Prime (1^2+6^2)
41: Pythagorean Prime (4^2+5^2)
53: Pythagorean Prime (2^2+7^2)
2: Khong
3: Khong
7: Khong
11: Khong
19: Khong