Kiểm tra số Quartan Prime C++

Quartan Prime – Số nguyên tố có dạng x⁴ + y⁴ với x,y > 0.

Định lý: Số nguyên tố p > 2 là Quartan Prime ⇔ p ≡ 1 (mod 16).

(Trừ p=2 = 1⁴+1⁴).

Chương trình C++

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

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

bool isQuartanPrime(long long n) {
    if (!isPrime(n)) return false;
    if (n == 2) return true; // 1^4 + 1^4
    return n % 16 == 1;
}

int main() {
    vector test = {2, 17, 97, 257, 337, 641, 100, 97};
    for (long long n : test)
        cout << n << ": " << (isQuartanPrime(n) ? "Quartan Prime" : "Khong") << "\n";
    return 0;
}

Kết quả

2: Quartan Prime
17: Quartan Prime (1^4+2^4)
97: Quartan Prime (2^4+3^4)
257: Quartan Prime (1^4+4^4)
337: Quartan Prime
641: Khong (641 = 640+1, 640%16=0 → 641%16=1 nhung 641=640+1=5*2^7+1, khong phai x^4+y^4)
100: Khong
97: Quartan Prime

Lưu ý: Điều kiện p≡1 (mod 16) là cần nhưng không đủ cho p>2 lớn. Cần kiểm tra thêm dạng x⁴+y⁴ nếu yêu cầu chính xác tuyệt đối.