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

1613551

#include <stdio.h>

main() {
        int a = 0, b = 0, c = 0;
        for (a = 2; a <= 10000; a++) {
                for (b = 2;  b <= (a / 2); b++) {

                        if (a % b != 0) {
                                c += 1;
                        }
                }

        }
        printf("10000以为一共有%d个素数\n", c);


        return 0;
}

最佳答案

月排行榜 / 总排行榜

风车呼呼呼

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

#include <stdio.h>

main() {
        int a = 0, b = 0, c = 0;
        for (a = 2; a <= 10000; a++) {
                for (b = 2;  b <= (a / 2); b++) {

                        if (a % b != 0&&b==a/2) {
                                c += 1;
                        }
                        if(a%b==0)
                        {break;}
                }

        }
        printf("10000以为一共有%d个素数\n", c);


        return 0;
}

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;
}

傻眼貓咪

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

#include <stdio.h>

int isPrime(int num){
    if(num < 2) return 0;
    else if (num == 2) return 1;
    for(int n = 2; n < (num >> 1) + 1; n++){
        if(!(num % n)) return 0;
    }
    return 1;
}

int main()
{
    int sum = 0;
    for(int num = 0; num < 10000; num++){
        if(isPrime(num)) sum++;
    }
    printf("%d", sum);
    return 0;
}

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；

#include <stdio.h>

int main()
{
        int count = 2; // 已知2和3是素数
        int i, j;
        _Bool flag = 1;

        for (i = 5; i < 10000; i++)
        {
                for (j = 2; j < i / 2; j++)
                {
                        if (i % j == 0)
                        {
                                flag = 0;
                                break;
                        }
                }

                if (flag)
                {
                        count++;
                }
                else
                {
                        flag = 1;
                }
        }

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

        return 0;
}

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）本身就有问题，所以就试着猜想了一下你的逻辑， ...

这是小甲鱼的程序

#include <stdio.h>

int main() {
        int count = 2; // 已知2和3是素数
        int i, j;
        _Bool flag = 1;

        for (i = 5; i < 10000; i++) {
                for (j = 2; j < i / 2; j++) {
                        if (i % j == 0) {
                                flag = 0;
                                break;
                        }
                }

                if (flag) {
                        count++;
                } else {
                        flag = 1;
                }
        }

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

        return 0;
}

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

if (flag) {
                        count++;
                } else {
                        flag = 1;
                }

风车呼呼呼

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语言的运行逻辑是啥