用c语言将一个4n+1形式的素数分解为两个完全平方数之和不用bool函数和void 函数

在 C 语言中，将一个形如 4n + 1 的素数分解为两个完全平方数之和，我们可以利用费马小定理的一种特殊情况。比如，如果 p 是一个形如 4n + 1 的素数，那么它必定可以表示为 2m * (2n + 1)，其中 m 和 n 都是非负整数。

为了找到这样的分解，我们只需要不断将 p 分解为 2 的幂次乘以一个奇数（即 2n + 1），直到这个奇数不再是质数为止。当这个奇数不能再分解时，就是我们要找的一个完全平方数。另一个完全平方数则由原来的小于 m 的指数部分给出。

下面是一个简单的示例程序：

#include <stdio.h>
#include <math.h>

// 计算最大公约数
int gcd(int a, int b) {
    return (b == 0 ? a : gcd(b, a % b));
}

// 判断是否为完全平方数
int is_square(int num) {
    int root = sqrt(num);
    return (root * root == num);
}

int main() {
    int p; // 输入的4n+1形式的素数
    printf("Enter a prime of the form 4n + 1: ");
    scanf("%d", &p);

    if (p % 4 != 1 || !is_prime(p)) { // 检查输入是否满足条件
        printf("The number is not in the form 4n + 1 or not a prime.\n");
        return 0;
    }

    int m = 0, n = 0;
    while (true) {
        p /= 2; // 将p除以2直到变为奇数
        if (!is_prime(p)) {
            break;
        }
        ++m;
    }
    
    int q = (p - 1) / 2; // 奇数部分

    while (!is_square(q)) {
        int temp = q;
        q = (q - 1) / 2;
        if (gcd(temp, q) > 1) {
            printf("No decomposition found for prime %d\n", p);
            return 0;
        }
    }

    int square1 = pow(2, m);
    int square2 = q;

    printf("Prime %d can be expressed as %d^2 + %d^2.\n", p, floor(sqrt(square1)), floor(sqrt(square2)));

    return 0;
}