输入一个自然数，用c语言判断是否为素数，其是否为4n+1形式的素数，讲他分解为两个平方数之和

在 C 语言中，我们可以编写一段程序来判断一个给定的自然数 n 是否为素数，并检查它是否可以表示为 4n + 1 形式的素数。同时，我们将展示如何找到这样的数可以分解为两个平方数之和，如果存在的话。注意，对于大质数，直接枚举求解可能会非常耗时，这里我们只提供基本算法。

#include <stdio.h>
#include <stdbool.h>

// 判断是否为素数
bool isPrime(int num) {
    if (num <= 1) return false;
    for (int i = 2; i * i <= num; ++i) {
        if (num % i == 0)
            return false;
    }
    return true;
}

// 检查是否为形如 4n + 1 的素数
bool isForm4nPlusOne(int num) {
    return num > 2 && num % 4 == 1 && isPrime(num);
}

// 求解两个平方数之和
void sumOfSquares(int num, int* a, int* b) {
    for (int a2 = 1; a2 * a2 <= num / 2; ++a2) {
        int b2 = num / (2 * a2) - a2;
        if (b2 >= a2 && (b2 * b2) == ((num / (2 * a2)) - a2) * ((num / (2 * a2)) - a2))
            break;
        // 另一种情况，考虑完全平方数
        int b3 = sqrt(num - a2 * a2);
        if (b3 * b3 == num - a2 * a2 && b3 > a2) {
            *a = a2;
            *b = b3;
            return;
        }
    }
    printf("No decomposition found for %d\n", num);
}

int main() {
    int input;
    printf("Enter a natural number: ");
    scanf("%d", &input);

    if (isForm4nPlusOne(input)) {
        printf("%d is a prime of the form 4n + 1.\n", input);
    } else {
        printf("%d is not of the form 4n + 1 or not prime.\n", input);
    }

    int a, b;
    sumOfSquares(input, &a, &b);
    printf("If it can be expressed as a sum of squares, it's (%d)^2 + (%d)^2.\n", a, b);

    return 0;
}