c语言编程：判断N是否为质数，要求时间复杂度为根号N

在C语言中，判断一个正整数N是否为质数可以通过检查从2到√N之间的所有整数是否能整除N来实现。如果在这个区间内没有任何数能整除N，则N为质数。这是因为如果N不是质数，那么它必定有一个因子不大于其平方根。以下是一个简单的C语言函数，用于判断一个数是否为质数：

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

// 函数用于判断N是否为质数
int isPrime(int N) {
    if (N <= 1) return 0; // 0和1不是质数
    if (N <= 3) return 1; // 2和3是质数
    if (N % 2 == 0 || N % 3 == 0) return 0; // 排除能被2和3整除的数

    // 只需要检查到sqrt(N)即可
    for (int i = 5; i * i <= N; i += 6) {
        if (N % i == 0 || N % (i + 2) == 0) {
            return 0; // 如果N能被i或i+2整除，则N不是质数
        }
    }
    return 1; // 如果没有找到任何因子，则N是质数
}

int main() {
    int number;
    printf("请输入一个整数：");
    scanf("%d", &number);
    if (isPrime(number)) {
        printf("%d 是质数。\n", number);
    } else {
        printf("%d 不是质数。\n", number);
    }
    return 0;
}

这段代码首先处理了小于等于1的数以及2和3的特殊情况，然后使用一个for循环从5开始，每次增加6，只检查5和它之后的每个数以及这个数加2（因为所有质数除了2和3之外，都在6的倍数的基础上加1或减1的位置上）。循环结束的条件是`i * i <= N`，这样可以确保检查的范围在√N之内。如果在这个范围内发现N有因子，则返回0表示N不是质数；否则，返回1表示N是质数。