[已解决]求质数

lsmCC

1. #include <iostream>
   
2. using namespace std;
   
3. int main()
   
4. {
   
5.     int n,j=0,i=0;
   
6.     cin>>n;
   
7.     for(int i=2;i<=n;i++)
   
8.     {
   
9.         int flag=0;
   
10.         for(int j=2;j<=i;j++)
    
11.         {      
    
12.             if(i%j==0)
    
13.             {
    
14.                 flag=1;
    
15.                 break;
    
16.             }
    
17.         }
    
18.         if(flag==0)
    
19.         {
    
20.             cout << i <<' ';
    
21.         }
    
22.       
    
23.          
    
24.     }
    
25.     return 0;
    
26. }

复制代码

为什么输出不了呢 ，还有其他求质数的方法吗

最佳答案

月排行榜 / 总排行榜

Mike_python小

2023-10-7 11:19:12

问题分析：

在给定的代码中，出现了两个问题。

首先是变量 flag 的位置不正确。在当前的代码中，flag 在内层循环中定义，并且每次迭代都会被重新赋值为 0，导致无法正确判断是否为质数。为了解决这个问题，我们应该将变量 flag 的定义放到外层循环之前，并在每次循环开始之前将其重置为 0。

其次是在判断是否为质数的内层循环中，变量 j 的范围应该是从 2 到 i-1，而不是从 2 到 i。因为一个数除了 1 和它本身以外，不能被其他数整除才能是质数。

问题解决：

修正以上问题后，代码应该能够正确输出质数。

同时，在求质数的算法中，还有一些优化的方法可以提高效率。例如，可以只遍历小于等于 sqrt(i) 的数去判断是否能整除，因为如果 i 能被大于 sqrt(i) 的数整除，那么一定也能被小于 sqrt(i) 的数整除。这样可以减少循环次数。

下面是修正问题并进行优化后的代码：

2. #include <iostream>
3. #include <cmath>
4. using namespace std;
6. int main() {
7.     int n;
8.     cin >> n;
10.     for (int i = 2; i <= n; i++) {
11.         int flag = 0;
12.         for (int j = 2; j <= sqrt(i); j++) {
13.             if (i % j == 0) {
14.                 flag = 1;
15.                 break;
16.             }
17.         }
18.         if (flag == 0) {
19.             cout << i << ' ';
20.         }
21.     }
23.     return 0;
24. }

复制代码

希望能够解决你的问题！如果还有其他问题，请随时提问。

球一个最佳答案谢谢啦！这对我非常重要！

跳转到最佳答案楼层

Mike_python小

问题分析：

在给定的代码中，出现了两个问题。

首先是变量 flag 的位置不正确。在当前的代码中，flag 在内层循环中定义，并且每次迭代都会被重新赋值为 0，导致无法正确判断是否为质数。为了解决这个问题，我们应该将变量 flag 的定义放到外层循环之前，并在每次循环开始之前将其重置为 0。

其次是在判断是否为质数的内层循环中，变量 j 的范围应该是从 2 到 i-1，而不是从 2 到 i。因为一个数除了 1 和它本身以外，不能被其他数整除才能是质数。

问题解决：

修正以上问题后，代码应该能够正确输出质数。

同时，在求质数的算法中，还有一些优化的方法可以提高效率。例如，可以只遍历小于等于 sqrt(i) 的数去判断是否能整除，因为如果 i 能被大于 sqrt(i) 的数整除，那么一定也能被小于 sqrt(i) 的数整除。这样可以减少循环次数。

下面是修正问题并进行优化后的代码：

2. #include <iostream>
3. #include <cmath>
4. using namespace std;
6. int main() {
7.     int n;
8.     cin >> n;
10.     for (int i = 2; i <= n; i++) {
11.         int flag = 0;
12.         for (int j = 2; j <= sqrt(i); j++) {
13.             if (i % j == 0) {
14.                 flag = 1;
15.                 break;
16.             }
17.         }
18.         if (flag == 0) {
19.             cout << i << ' ';
20.         }
21.     }
23.     return 0;
24. }

复制代码

希望能够解决你的问题！如果还有其他问题，请随时提问。

球一个最佳答案谢谢啦！这对我非常重要！

isdkz

这段代码的问题在于变量名重复了，外层循环的变量i和内层循环的变量j重复了，可以将内层循环的变量名改成其他名字。同时，这段代码的时间复杂度较高，可以使用更高效的算法来求质数，如埃氏筛法和欧拉筛法等。

以下是修改后的代码和使用埃氏筛法求质数的示例代码：

修改后的代码：

#include <iostream>
using namespace std;
int main()
{
    int n;
    cin >> n;
    for (int i = 2; i <= n; i++)
    {
        int flag = 0;
        for (int j = 2; j <= i; j++)
        {
            if (i % j == 0)
            {
                flag = 1;
                break;
            }
        }
        if (flag == 0)
        {
            cout << i << ' ';
        }
    }
    return 0;
}

使用埃氏筛法求质数的代码：

#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 1000000;
bool isPrime[MAXN + 1];
int main()
{
    int n;
    cin >> n;
    memset(isPrime, true, sizeof(isPrime));
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i * i <= n; i++)
    {
        if (isPrime[ i])
        {
            for (int j = i * i; j <= n; j += i)
            {
                isPrime[j] = false;
            }
        }
    }
    for (int i = 2; i <= n; i++)
    {
        if (isPrime[ i])
        {
            cout << i << ' ';
        }
    }
    return 0;
}