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;
}