题解 | 素数判断

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

int main() {
    int T;
    scanf("%d",&T);
    for(int i = 0;i < T;i++)
    {
        int n;
        scanf("%d",&n);
        if (n <= 1)
        {
            printf("No\n");
            continue;
        }
        bool isprime = true;
        for (int j = 2;j*j <= n;j++)
        {
            if(n % j == 0)
            {
                isprime = false;
                break;
            }
        }
        if(isprime)
        {
            printf("Yes\n");
        }
        else {
            printf("No\n");
        }
    }
    return 0;
}

1.引入布尔类型表示状态

2.将算法复杂度从O(n)降至O(根下n)