[已解决]求10000以内的素数个数

知我枯荣

求 10000 以内的素数个数。

哪儿错了

#include <stdio.h>
#include <math.h>
int main()
{
        int count = 2;
        int i, j,k;
               
        for (i = 5; i < 10000; i++)
        {
                k=(int)sqrt((double)i);
                for(j=2;j<=k;j++)
                {
                         if (i % j != 0)
                        {
                               count++;
                        }
                                }
                       
        }

        printf("10000以内共有%d个素数！\n", count);

        return 0;
}

最佳答案

月排行榜 / 总排行榜

柠檬西瓜汁

2021-4-14 18:31:36

第二层for语句中if语句有问题，例如数字7是素数，当j=2时，if条件成立，素数加1；当j=3时，if条件依然成立，素数会再次加1，导致一个素数加的次数可能不止一次，最后结果出错。
我们可以换个想法，在2~那个之间，如果有能被莫一整数整除，那它一定不是素数，是合数，求出合数个数后，其余的就是素数的个数啦！程序如下：
#include <stdio.h>
#include <math.h>
int main()
{
        int count = 2;
        int i, j,k;
               
        for (i = 5; i < 10000; i++)
        {
                k=(int)sqrt((double)i);
                for(j=2;j<=k;j++)
                {
                         if (i % j == 0)
                        {
                               count++;break;
                        }
                }
                       
        }
                count=9999-count;

        printf("10000以内共有%d个素数！\n", count);

        return 0;
}
这个程序是经过楼主的修改的，可以看到：如果i一旦能被j整除，合数加1，然后退出内层for循环，进行下一个数字的判断。（if语句中有break,一旦执行将退出内层循环）

跳转到最佳答案楼层

柠檬西瓜汁

第二层for语句中if语句有问题，例如数字7是素数，当j=2时，if条件成立，素数加1；当j=3时，if条件依然成立，素数会再次加1，导致一个素数加的次数可能不止一次，最后结果出错。
我们可以换个想法，在2~那个之间，如果有能被莫一整数整除，那它一定不是素数，是合数，求出合数个数后，其余的就是素数的个数啦！程序如下：
#include <stdio.h>
#include <math.h>
int main()
{
        int count = 2;
        int i, j,k;
               
        for (i = 5; i < 10000; i++)
        {
                k=(int)sqrt((double)i);
                for(j=2;j<=k;j++)
                {
                         if (i % j == 0)
                        {
                               count++;break;
                        }
                }
                       
        }
                count=9999-count;

        printf("10000以内共有%d个素数！\n", count);

        return 0;
}
这个程序是经过楼主的修改的，可以看到：如果i一旦能被j整除，合数加1，然后退出内层for循环，进行下一个数字的判断。（if语句中有break,一旦执行将退出内层循环）

wp231957

这种问题最好是把判断一个数是否是素数单独提出一个函数来

ba21

#include <stdio.h>
#include <math.h>
int main()
{
        int count = 2; 
        int i, j,k;
                int flag; // 用于标记这个数是否为素数。
                
        for (i = 5; i < 10000; i++)
        {
                k=(int)sqrt(i);
                                flag = 1; // 先假设这个数为素数
                for(j=2;j<=k;j++)
                {
                         if (i % j == 0) // 不是素数
                        {
                                                         flag = 0;
                               break;
                        }
                }
                                if(flag)
                                {
                                        count++;
                                }
                       
        }

        printf("10000以内共有%d个素数！\n", count);

        return 0;
}

肖-肖

 for(j=2;j<=k;j++)
                {
                         if (i % j != 0)
                        {
                               count++;
                        }
                                }

这么写不对!
比如i是9，9%2=1 ->1!=0->count+1-->不对的
我改成了如下这样:

#include <stdio.h>
#include <math.h>
int main()
{
    int count = 2;
    int i,j,k;

    for (i = 5; i <= 10000; i++)
    {
        //sqrt() 用来求给定值的平方根 所以k求得是i得平方根
        k=(int)sqrt((double)i);

        for(j=2;j<=k;j++)
        {
            if (i % j == 0)
            {
                //count++;
                //说明不是素数了,直接跳出循环
                break;
            }
        }
        if(j>k)
            count++;
    }

    printf("10000以内共有%d个素数！\n", count);

    return 0;
}

运行结果如下图:

还符合了小甲鱼得要求!!!

OK 希望对你有用哦

知我枯荣

肖-肖 发表于 2021-4-14 19:33
这么写不对!
比如i是9，9%2=1 ->1!=0->count+1-->不对的
我改成了如下这样:

感谢大佬，大佬和楼下讲的都很有道理，原谅我把最佳答案给新鱼友啦

知我枯荣

柠檬西瓜汁 发表于 2021-4-14 18:31
第二层for语句中if语句有问题，例如数字7是素数，当j=2时，if条件成立，素数加1；当j=3时，if条件依然成立 ...

我懂了，感谢感谢

知我枯荣

ba21 发表于 2021-4-14 18:51

感谢大佬，这一题学会了三种方法

肖-肖

知我枯荣 发表于 2021-4-15 01:18
感谢大佬，大佬和楼下讲的都很有道理，原谅我把最佳答案给新鱼友啦

嗯嗯 没事，懂了就好

柠檬西瓜汁

知我枯荣 发表于 2021-4-15 01:21
我懂了，感谢感谢

哇啊啊啊啊！本鱼友表示受宠若惊