[已解决]为甚马不能判断质数呀

FlyingEgg

#include<stdio.h>
int main()
{
        int a,i,flag;
       
        scanf("%d",&a);
        for(i=2;i<a;i++)
        {
                if(a%i==0)
                {
                        flag=1;
                        break;
                }
               
        }
       
if(flag==1)
{
       
        printf("%d不是素数",a);
       
}
else
{
        printf("%d是素数",a);
}

return 0;
}

最佳答案

月排行榜 / 总排行榜

foxiangzun

2022-3-10 18:20:43

我这边运行你的代码是 OK 的。。



代码本身的逻辑没有问题，但是范围没有做好控制，0，1，这两个数既不是质数，也不是和数，所以需要判断出来，另外，这样判断的话，效率比较低，算法效率是 O(n^2)，用埃拉托色尼算法，可以降低复杂度，下面是代码：

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int i, j;
    int a[101];
    int b[4] = {2, 3, 5, 7};
    for (i = 1; i < 101; i++)
    {
        a[i] = 1;
    }
    a[1] = 0;
    for (i = 1; i < 101; i++)
    {
        for (j = 0; j < 4; j++)
        {
            if (i != b[j] && i % b[j] == 0)
            {
                a[i] = 0;
            }
        }
    }
    for (i = 1; i < 101; i++)
    {
        if (a[i] == 1)
        {
            printf("%d\t", i);
        }
    }
    return 0;
}

大体思路就是：
1、确立范围，然后把范围先平方根一把（代码里没有体现出来，但是范围是 100）；
2、将2到平方根之间的质数先找到（所以数组b里是 2，3，5，7）；
3、将这些质数在步骤1的范围的倍数都找到，然后做标记排除掉；
4、最后将未标记的数输出，得到的就都是质数了；

算法复杂度约为O(n*√n)，在此基础上再试试看

跳转到最佳答案楼层

jackz007

#include<stdio.h>
int main(void)
{
        int a , i , flag                                                 ;
        scanf("%d" , & a)                                                ;
        flag = 0                                                         ;
        if(a > 1) {
                if(a % 2 && a % 3 && a % 5 && a % 7) {
                        for(flag = 1 , i = 3 ; i * i < a + 1 ; i += 2) {
                                if(! (a % i)) {
                                        flag = 0                         ;
                                        break                            ;
                                }
                        }
                } else if(a == 2 || a == 3 || a == 5 || a == 7) flag = 1 ;
        }
        if(! flag) printf("%d 不是素数\n" , a)                           ;
        else printf("%d 是素数\n" , a)                                   ;
}

foxiangzun

我这边运行你的代码是 OK 的。。



代码本身的逻辑没有问题，但是范围没有做好控制，0，1，这两个数既不是质数，也不是和数，所以需要判断出来，另外，这样判断的话，效率比较低，算法效率是 O(n^2)，用埃拉托色尼算法，可以降低复杂度，下面是代码：

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int i, j;
    int a[101];
    int b[4] = {2, 3, 5, 7};
    for (i = 1; i < 101; i++)
    {
        a[i] = 1;
    }
    a[1] = 0;
    for (i = 1; i < 101; i++)
    {
        for (j = 0; j < 4; j++)
        {
            if (i != b[j] && i % b[j] == 0)
            {
                a[i] = 0;
            }
        }
    }
    for (i = 1; i < 101; i++)
    {
        if (a[i] == 1)
        {
            printf("%d\t", i);
        }
    }
    return 0;
}

大体思路就是：
1、确立范围，然后把范围先平方根一把（代码里没有体现出来，但是范围是 100）；
2、将2到平方根之间的质数先找到（所以数组b里是 2，3，5，7）；
3、将这些质数在步骤1的范围的倍数都找到，然后做标记排除掉；
4、最后将未标记的数输出，得到的就都是质数了；

算法复杂度约为O(n*√n)，在此基础上再试试看

FlyingEgg

foxiangzun 发表于 2022-3-10 18:20
我这边运行你的代码是 OK 的。。

谢谢你的回答   但不知道为什么我这边一直跑不对 一直显示不是质数 我再研究一下吧