[已解决]求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

1. #include <stdio.h>
   
2. #include <math.h>
   
3. int main()
   
4. {
   
5.         int count = 2;
   
6.         int i, j,k;
   
7.                 int flag; // 用于标记这个数是否为素数。
   
8.                
   
9.         for (i = 5; i < 10000; i++)
   
10.         {
    
11.                 k=(int)sqrt(i);
    
12.                                 flag = 1; // 先假设这个数为素数
    
13.                 for(j=2;j<=k;j++)
    
14.                 {
    
15.                          if (i % j == 0) // 不是素数
    
16.                         {
    
17.                                                          flag = 0;
    
18.                                break;
    
19.                         }
    
20.                 }
    
21.                                 if(flag)
    
22.                                 {
    
23.                                         count++;
    
24.                                 }
    
25.                        
    
26.         }
    
27. 
    
28.         printf("10000以内共有%d个素数！\n", count);
    
29. 
    
30.         return 0;
    
31. }

复制代码

肖-肖

1. for(j=2;j<=k;j++)
   
2.                 {
   
3.                          if (i % j != 0)
   
4.                         {
   
5.                                count++;
   
6.                         }
   
7.                                 }

复制代码

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

1. #include <stdio.h>
   
2. #include <math.h>
   
3. int main()
   
4. {
   
5.     int count = 2;
   
6.     int i,j,k;
   
7. 
   
8.     for (i = 5; i <= 10000; i++)
   
9.     {
   
10.         //sqrt() 用来求给定值的平方根 所以k求得是i得平方根
    
11.         k=(int)sqrt((double)i);
    
12. 
    
13.         for(j=2;j<=k;j++)
    
14.         {
    
15.             if (i % j == 0)
    
16.             {
    
17.                 //count++;
    
18.                 //说明不是素数了,直接跳出循环
    
19.                 break;
    
20.             }
    
21.         }
    
22.         if(j>k)
    
23.             count++;
    
24.     }
    
25. 
    
26.     printf("10000以内共有%d个素数！\n", count);
    
27. 
    
28.     return 0;
    
29. }
    

复制代码

运行结果如下图:

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

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
我懂了，感谢感谢

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