[已解决]求质数

lsmCC

#include <iostream>
using namespace std;
int main()
{
    int n,j=0,i=0;
    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;
}

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

最佳答案

月排行榜 / 总排行榜

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) 的数整除。这样可以减少循环次数。

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

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

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

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

跳转到最佳答案楼层

Mike_python小

问题分析：

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

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

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

问题解决：

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

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

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

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

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

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

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