这是一个从2-100里找质数的代码,但我看不明白,哪个聪明人可以给我解释一下(我很不聪明😭))

img

img


这是一个从2-100里找质数的代码,但我看不明白,哪个聪明人可以给我解释一下(我很不聪明😭))

这是用素数表排除法(即a[101])来优化素数的计算
首先把 a[] 的全部元素设置为1
然后从2开始,把a[2] a[4] a[6]... 全部设置为0
然后在a[2] a[4]之前的a[3] == 1,所以3就是素数
然后把a[3] a[6] a[9] a[12] ... 全部设置为0
那么在a[6]之前的5又是素数
以此类推
到最后,所有为1,也就是没有排除的,都是素数了。
这种方法也叫做筛选法。

通过迭代标记每个质数的倍数为合数,只留下质数未标记。最后,它打印出数组中所有剩余的非零值,这些值对应于质数。(我个人感觉这有些类似于埃氏筛的思想)

不知道你这个问题是否已经解决, 如果还没有解决的话:
  • 你可以参考下这个问题的回答, 看看是否对你有帮助, 链接: https://ask.csdn.net/questions/7681619
  • 以下回答来自chatgpt:

    该代码是一个循环嵌套,外层循环会遍历2到100之间的所有数字,内层循环遍历每个数字,用取余运算判断该数字是否为质数。具体解释如下:

    1. 首先,循环变量y从100开始,每次加1,一直循环直到y的值等于200。这个过程可以通过以下代码表示:
    for (y = 100; y <= 200; y++)
    
    1. 在外层循环内部,定义变量flag和变量n,flag表示是否为质数的标志,初值设为1,n表示内层循环的循环变量,从2开始循环到y-1,判断y是否为n的倍数。如果是,flag就变成0,表示y不是质数。这个过程可以通过以下代码表示:
    int n = 0;
    int flag = 1;
    for (n = 2; n < y; n++)
    {
        if (y % n == 0)
        {
            flag = 0;
            break;
        }
    }
    
    1. 在内层循环结束后,判断标志变量flag是否为1,如果是,就输出这个数字。这个过程可以通过以下代码表示:
    if (flag == 1)
    {
        printf("%d ", y);
    }
    

    完整的代码如下:

    #include<stdio.h>
    int main()
    {
        int y = 0;
        for (y = 100; y <= 200; y++)
        {
            int n = 0;
            int flag = 1;
            for (n = 2; n<y ; n++)
            {
                if (y % n == 0)
                {
                    flag = 0;
                    break;
                }
            }
            if (flag == 1)
            {
                printf("%d ", y);
            }
        }
        return 0;
    }
    

    值得注意的是,该算法判断质数的效率并不高,因为它用到了循环嵌套,时间复杂度较高。在实际应用中,应该使用更高效的算法来判断素数。


如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^