Số nguyên tố thỏa mãn là tổng của hai số chính phương

27
Lập trình C++

Bài toán. Những số nguyên tố chia cho 4 dư 1 thì luôn biểu diễn được dưới dạng tổng của 2 số chính phương. Nhập số n, kiểm tra xem n có là số nguyên tố hay không? Nếu thỏa mãn ghi ra hai số chính phương có tổng bằng n. Ngược lại, ghi ra -1. Ví dụ: 

BDNT.INP

BDNT.OUT

61

25 36

Code tham khảo:

#include <iostream>
#include <cmath>
using namespace std;
int nguyenTo(int n) {
    if (n < 2) return 0;
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) return 0;
    }
    return 1;
}
int cp(int n) {
    if ((float)sqrt(n) == (int)sqrt(n))
        return 1;
    else return 0;
}
int main() {
    freopen("BDNT.INP","r",stdin);
    freopen("BDNT.OUT","w",stdout);
    int n;
    cin >> n;
    if(nguyenTo(n)) {
        if (n % 4 == 1 || n == 2) {
            int a = 1;
            while (!cp(a) || !cp(n-a)) {
                a++;
            }
            cout << a << " " << n-a;
        } else cout << -1;
    } else cout << -1;
    return 0;
}