【C语言】通过代码计算100~200之间的所有素数。

1.

素数 i 只能被1 和 i 整除， 所以考虑使用 2 ~ i-1 来除 i 。

代码如下：       

int main()
{
    int COUNT = 0;
    int i = 0;
  
    for (i = 100 ; i <= 200 ; i++)
    {
        int j = 0;
        for (j =2; j< i ; j++)         //判断i是否为素数， 用 2~i-1 的数字除i， 看能不能整除。
        {
            if (i %j == 0)
                break;
        }
        
        if(j == i)
        {

            COUNT++;
            printf("%d ", j);
        }


    }
    printf("n%d ", COUNT);
    return 0;
}

通过变量count可以计算100~200之间有多少个素数。

目的实现。

2. 优化代码

        如果 i = a*b ， 那么 a ， b中一定有一个数 <= 根号i ，因此不必计算 2~ i-1 的所有数字，只需计算  2~ 根号i 。

需要使用sqrt()函数进行开平方， 需引用头文件 #include

代码如下：

#include 

int main()
{
    int COUNT = 0;
    int i = 0;

    for (i = 100 ; i <= 200 ; i ++)
    {
        int flag = 1;
        int j = 0;
        for (j =2; j<= sqrt(i) ; j++)        //一个数的两个因子 一定有一个小于 开平方它
        {
            if (i %j == 0)
              {

               flag = 0;                        //sqrt() 开平方， 用math.h
                break;
              }
        }


        if(flag == 1)
        {

            COUNT++;
            printf("%d ", i);
        }


    }
    printf("n%d ", COUNT);
    return 0;
}

使用 flag 作为标记。

3. 进一步优化

由于100~200之间的偶数均能被2 整除， 所以都不是素数。我们只取奇数。

对for循环进行改进。

代码如下：

#include 

int main()
{
    int COUNT = 0;
    int i = 0;

    for (i = 101 ; i <= 200 ; i += 2)
    {
        int flag = 1;
        int j = 0;
        for (j =2; j<= sqrt(i) ; j++)            //一个数的两个因子 一定有一个小于 开平方它
        {
            if (i %j == 0)
              {

               flag = 0;                               //sqrt() 开平方， 用math.h
                break;
              }
        }


        if(flag == 1)
        {

            COUNT++;
            printf("%d ", i);
        }


    }
    printf("n%d ", COUNT);
    return 0;
}

代码编写完毕。