[已解决]为啥我这个程序算出来的素数会那么大啊

1613551

1. #include <stdio.h>
   
2. 
   
3. main() {
   
4.         int a = 0, b = 0, c = 0;
   
5.         for (a = 2; a <= 10000; a++) {
   
6.                 for (b = 2;  b <= (a / 2); b++) {
   
7. 
   
8.                         if (a % b != 0) {
   
9.                                 c += 1;
   
10.                         }
    
11.                 }
    
12. 
    
13.         }
    
14.         printf("10000以为一共有%d个素数\n", c);
    
15. 
    
16. 
    
17.         return 0;
    
18. }

复制代码

最佳答案

月排行榜 / 总排行榜

风车呼呼呼

2022-4-10 15:08:26

这完全是设计思路上的问题了。。。
我猜你的思路是：
10000以内的素数，那就用a遍历2~10000；
然后用b来从2开始遍历，记录下其中的素数；

我给你几个例子，你想想就知道问题有多大了
1.
a=7时，b<=(a/2)=3,当b=3时，a%b!=0,计数+1
a=8时，b<=(a/2)=4,当b=3时，a%b!=0,计数+1
（素数3被重复统计，同理后面每一个a（非3的倍数）都会统计一次素数3）

2.
很明显，4并不是一个素数
但在你的程序中
a=9时，b<=(a/2)=4，当b=4时，9%4!=0，计数+1
（除不尽就算作是素数，这明显离谱了）

跳转到最佳答案楼层

1613551

这是题目

HandsonYe

1. #include <stdio.h>
   
2. 
   
3. main() {
   
4.         int a = 0, b = 0, c = 0;
   
5.         for (a = 2; a <= 10000; a++) {
   
6.                 for (b = 2;  b <= (a / 2); b++) {
   
7. 
   
8.                         if (a % b != 0&&b==a/2) {
   
9.                                 c += 1;
   
10.                         }
    
11.                         if(a%b==0)
    
12.                         {break;}
    
13.                 }
    
14. 
    
15.         }
    
16.         printf("10000以为一共有%d个素数\n", c);
    
17. 
    
18. 
    
19.         return 0;
    
20. }

复制代码

1613551

HandsonYe 发表于 2022-4-10 14:12

我不理解，为什么不加上if（a%b）==0然后break退出循环的话，素数会多了那么多？

1613551

HandsonYe 发表于 2022-4-10 14:12

明明没有满足不等于0这个条件应该是不会增加素数的啊，c语言好奇怪啊

风车呼呼呼

这完全是设计思路上的问题了。。。
我猜你的思路是：
10000以内的素数，那就用a遍历2~10000；
然后用b来从2开始遍历，记录下其中的素数；

我给你几个例子，你想想就知道问题有多大了
1.
a=7时，b<=(a/2)=3,当b=3时，a%b!=0,计数+1
a=8时，b<=(a/2)=4,当b=3时，a%b!=0,计数+1
（素数3被重复统计，同理后面每一个a（非3的倍数）都会统计一次素数3）

2.
很明显，4并不是一个素数
但在你的程序中
a=9时，b<=(a/2)=4，当b=4时，9%4!=0，计数+1
（除不尽就算作是素数，这明显离谱了）

yzzc

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
int main(void)
{
        int i, j,k=0;
        for (i = 2; i < 10000; i++)
        {
                for (j = 2; j < i; j++)
                {
                        if (i % j == 0)
                                break;
                }
                if (j >= i)
                {
                        printf("%d ", i); k++;
                }
        }
        printf("\n总共有：%d", k);
        return 0;
}

傻眼貓咪

怕乱就另外写个函数判断素数：

1. #include <stdio.h>
   
2. 
   
3. int isPrime(int num){
   
4.     if(num < 2) return 0;
   
5.     else if (num == 2) return 1;
   
6.     for(int n = 2; n < (num >> 1) + 1; n++){
   
7.         if(!(num % n)) return 0;
   
8.     }
   
9.     return 1;
   
10. }
    
11. 
    
12. int main()
    
13. {
    
14.     int sum = 0;
    
15.     for(int num = 0; num < 10000; num++){
    
16.         if(isPrime(num)) sum++;
    
17.     }
    
18.     printf("%d", sum);
    
19.     return 0;
    
20. }

复制代码

1. 1229

复制代码

她让我孤立无援

#include <stdio.h>
int main()
{
        int a,b,c=0;
       
        for(a=2;a<10000;a++)
        {
                for(b=2;b<a;b++)
                {
                        if(a%b==0)
                        {
                               
                                break;       
                        }
               
                }
                if(b>=a)
                {
                        c=c+1;
                }
               
       
        }
        printf("10000以内的素数有%d个",c);
       
}
1229

1613551

风车呼呼呼 发表于 2022-4-10 15:08
这完全是设计思路上的问题了。。。
我猜你的思路是：
10000以内的素数，那就用a遍历2~10000；

不好意思，因为昨天有事，所以没有学c，你的回答我看了，我大概了解你的，但是你回答又感觉有点奇怪，素数难道不是只能被1和自身整除的数才叫素数吗，可你第二个回答，素数却做了除数，可是我计算的是a是不是除数

1613551

风车呼呼呼 发表于 2022-4-10 15:08
这完全是设计思路上的问题了。。。
我猜你的思路是：
10000以内的素数，那就用a遍历2~10000；

1. #include <stdio.h>
   
2. 
   
3. int main()
   
4. {
   
5.         int count = 2; // 已知2和3是素数
   
6.         int i, j;
   
7.         _Bool flag = 1;
   
8. 
   
9.         for (i = 5; i < 10000; i++)
   
10.         {
    
11.                 for (j = 2; j < i / 2; j++)
    
12.                 {
    
13.                         if (i % j == 0)
    
14.                         {
    
15.                                 flag = 0;
    
16.                                 break;
    
17.                         }
    
18.                 }
    
19. 
    
20.                 if (flag)
    
21.                 {
    
22.                         count++;
    
23.                 }
    
24.                 else
    
25.                 {
    
26.                         flag = 1;
    
27.                 }
    
28.         }
    
29. 
    
30.         printf("10000以内共有%d个素数！\n", count);
    
31. 
    
32.         return 0;
    
33. }

复制代码

1613551

风车呼呼呼 发表于 2022-4-10 15:08
这完全是设计思路上的问题了。。。
我猜你的思路是：
10000以内的素数，那就用a遍历2~10000；

我还是不理解，如果说素数会被重复计算的话，为什么小甲鱼这个程序不会呀

风车呼呼呼

1613551 发表于 2022-4-12 11:05
不好意思，因为昨天有事，所以没有学c，你的回答我看了，我大概了解你的，但是你回答又感觉有点奇怪，素 ...

啊是的，当时因为看你判断是否为素数的条件（是否计数+1）本身就有问题，所以就试着猜想了一下你的逻辑，并根据你的逻辑来举一些会出问题的反例

1613551

风车呼呼呼 发表于 2022-4-12 11:34
啊是的，当时因为看你判断是否为素数的条件（是否计数+1）本身就有问题，所以就试着猜想了一下你的逻辑， ...

你的逻辑我懂了，但是又好像不懂，就比如小甲鱼的程序为什么没有这个问题啊

1613551

风车呼呼呼 发表于 2022-4-12 11:34
啊是的，当时因为看你判断是否为素数的条件（是否计数+1）本身就有问题，所以就试着猜想了一下你的逻辑， ...

这是小甲鱼的程序

1. #include <stdio.h>
   
2. 
   
3. int main() {
   
4.         int count = 2; // 已知2和3是素数
   
5.         int i, j;
   
6.         _Bool flag = 1;
   
7. 
   
8.         for (i = 5; i < 10000; i++) {
   
9.                 for (j = 2; j < i / 2; j++) {
   
10.                         if (i % j == 0) {
    
11.                                 flag = 0;
    
12.                                 break;
    
13.                         }
    
14.                 }
    
15. 
    
16.                 if (flag) {
    
17.                         count++;
    
18.                 } else {
    
19.                         flag = 1;
    
20.                 }
    
21.         }
    
22. 
    
23.         printf("10000以内共有%d个素数！\n", count);
    
24. 
    
25.         return 0;
    
26. }

复制代码

为什么小甲鱼这样写的话却不会重复计算素数呢？

1. if (flag) {
   
2.                         count++;
   
3.                 } else {
   
4.                         flag = 1;
   
5.                 }

复制代码

风车呼呼呼

1613551 发表于 2022-4-12 11:26
我还是不理解，如果说素数会被重复计算的话，为什么小甲鱼这个程序不会呀

上面那个运行应该是没问题的。
这两个程序判断素数条件是完全相反的啊

你的是a除以b一旦除不尽，那就是素数。例：9%4!=0,你的程序就判断9是素数了
后面这个程序是，i一直遍历取余到（i/2），如果一旦取余等于0，那i就不是素数

1613551

风车呼呼呼 发表于 2022-4-12 11:34
啊是的，当时因为看你判断是否为素数的条件（是否计数+1）本身就有问题，所以就试着猜想了一下你的逻辑， ...

比如13是一个素数，它不能被2整除会让count+1,不能被3整除又会让count+，不能被4整数又会让count+1这样子

风车呼呼呼

1613551 发表于 2022-4-12 11:39
这是小甲鱼的程序

因为这段计数代码是放在j循环（判断素数代码段）的外面呀，一个i只对应一次可能计数的机会

1613551

风车呼呼呼 发表于 2022-4-12 11:40
上面那个运行应该是没问题的。
这两个程序判断素数条件是完全相反的啊

噢，我看懂了

1613551

风车呼呼呼 发表于 2022-4-12 11:40
上面那个运行应该是没问题的。
这两个程序判断素数条件是完全相反的啊

那么我还有最后一个问题，就是我不太清楚c语言的运行逻辑是啥