求1000以内的质数c语言

求1000以内的质数c语言

之前在做求1000以内的质数的时候，我们一般能想到的就是从3~（根号）no，逐一和no除，如果存在某个i使得  i|no成立的话，说明no不是质数（“i|no”是i整除除no的意思）；

在《明解c语言》上看到了一种与相似，但运算次数比其还少的。

#include <stdio.h>

int main(void)

{

    int i,no;

    int prime[];

    int ptr=;

    unsigned long counter=;

    prime[ptr++]=;          //这里是prime[0]=2,然后ptr再加加

    prime[ptr++]=;

    for(no=;no<;no+=)

    {

        int flag=;

        for(i=;counter++,prime[i]*prime[i]<=no;i++)   //counter++是因为接下来的prime[i]*prime[i]要作一次乘法运算，这样一来那么no除的只是小于根号no的的质数

        {

            counter++;

            if(no%prime[i]==)

            {

                flag=;

                break;

            }

        }

        if(!flag)        //flag=1，说明no并不是质数，反之no为质数

        {

            prime[ptr++]=no;

        }

    }

    for(i=;i<ptr;i++)

    {

        printf("%d\n",prime[i]);

    }

    printf("乘除运算的次数为：%lu\n",counter);

    return();

}