C语言学习记录——BC81 KiKi求质数个数

KiKi求质数个数_牛客题霸_牛客网 (nowcoder.com)

#include<stdio.h>
#include<math.h>//因为用到了sqrt()函数
int main()
{
    int i,j,a=0;//a为素数个数统计
    for(i=101;i<=997;i+=2)//三位数从101开始到997，因为100，998，999一看就不是素数
    {                    //然后是从101开始，每次加2，则跳过所有偶数，只看奇数，因为偶数肯定不是素数
        for(j=3;j<=sqrt(i);j+=2)//从3开始，用奇数除，因为上一步已经把偶数全跳过，检验从3开始的奇数一个一个试
        {                       //如果有哪个奇数能把i整除，则i不是素数则跳出j循环，此时j小于sqrt(i),a不累加
            if(i%j==0)
            {
                break;
            }
        }
        if(j>sqrt(i))//为什么是sqrt(i)呢？是因为非质数的成对因数每对较小的最大不超过sqrt(i),
                     //因此j从3开始奇数一个个比较一直到sqrt(i),还没有找到，则j就会因为循环完了
                     //所以大于sqrt(i)而跳出循环，此时我们用这个j>sqrt(i),来判断此时i为素数，a累加1
        {
            a++;
        }
    }
    printf("%d",a);
    return 0;
}

【C语言】判断一个数是否为素数（素数求解的N种境界）_c语言判断一个数为素数-CSDN博客

大家可以看这篇博客，写的很详细！！！