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

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)，用埃拉托色尼算法，可以降低复杂度，下面是代码：

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. int main()
   
5. {
   
6.     int i, j;
   
7.     int a[101];
   
8.     int b[4] = {2, 3, 5, 7};
   
9.     for (i = 1; i < 101; i++)
   
10.     {
    
11.         a[i] = 1;
    
12.     }
    
13.     a[1] = 0;
    
14.     for (i = 1; i < 101; i++)
    
15.     {
    
16.         for (j = 0; j < 4; j++)
    
17.         {
    
18.             if (i != b[j] && i % b[j] == 0)
    
19.             {
    
20.                 a[i] = 0;
    
21.             }
    
22.         }
    
23.     }
    
24.     for (i = 1; i < 101; i++)
    
25.     {
    
26.         if (a[i] == 1)
    
27.         {
    
28.             printf("%d\t", i);
    
29.         }
    
30.     }
    
31.     return 0;
    
32. }

复制代码

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

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

跳转到最佳答案楼层

jackz007

1. #include<stdio.h>
   
2. int main(void)
   
3. {
   
4.         int a , i , flag                                                 ;
   
5.         scanf("%d" , & a)                                                ;
   
6.         flag = 0                                                         ;
   
7.         if(a > 1) {
   
8.                 if(a % 2 && a % 3 && a % 5 && a % 7) {
   
9.                         for(flag = 1 , i = 3 ; i * i < a + 1 ; i += 2) {
   
10.                                 if(! (a % i)) {
    
11.                                         flag = 0                         ;
    
12.                                         break                            ;
    
13.                                 }
    
14.                         }
    
15.                 } else if(a == 2 || a == 3 || a == 5 || a == 7) flag = 1 ;
    
16.         }
    
17.         if(! flag) printf("%d 不是素数\n" , a)                           ;
    
18.         else printf("%d 是素数\n" , a)                                   ;
    
19. }

复制代码

foxiangzun

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



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

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. int main()
   
5. {
   
6.     int i, j;
   
7.     int a[101];
   
8.     int b[4] = {2, 3, 5, 7};
   
9.     for (i = 1; i < 101; i++)
   
10.     {
    
11.         a[i] = 1;
    
12.     }
    
13.     a[1] = 0;
    
14.     for (i = 1; i < 101; i++)
    
15.     {
    
16.         for (j = 0; j < 4; j++)
    
17.         {
    
18.             if (i != b[j] && i % b[j] == 0)
    
19.             {
    
20.                 a[i] = 0;
    
21.             }
    
22.         }
    
23.     }
    
24.     for (i = 1; i < 101; i++)
    
25.     {
    
26.         if (a[i] == 1)
    
27.         {
    
28.             printf("%d\t", i);
    
29.         }
    
30.     }
    
31.     return 0;
    
32. }

复制代码

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

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

FlyingEgg

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

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