找出一个数是否为质数

Question

代码显示错误结果...它显示 15,21 和许多其他奇数为质数但它们不是...如何解决问题？..我应该在主要部分编写什么代码[内部 int main()]?

#include<bits/stdc++.h>
using namespace std;
#define M 1000000
bool marked[M];



bool sieve(int n)
{
    for (int i = 3; i * i <= n; i += 2)
    {
        if (marked[i] == false)
        {
            for (int j = i * i; j <= n; j += i + i)
            {
                marked[j] = true;
            }
        }
    }
}
bool isPrime(int n)
{
    if (n < 2)
        return false;
    if (n == 2)
        return true;
    if (n % 2 == 0)
        return false;
    return marked[n] == false;
}
int main()
{
    int i,j,k,n,m;
    cin>>n;
    for(i=0; i<n; i++)
    {
        cin>>m;
        if(isPrime(m))
            cout<<"prime"<<endl;
        else
            cout<<"N"<<endl;
    }
}

是不是因为没有正确使用或调用函数导致的错误答案？......这种情况应该怎么办......

Answer 1

我的猜测是，由于您从未调用 sieve 函数，因此您的 marked 数组永远不会被填充。由于 marked 不是动态分配的，因此它在您的程序中被清零。因此，在您的 isPrime 函数中，所有奇数将通过您的 if 语句级联，然后命中 marked[n] == false 的部分，这将 return 为真，因为 marked[n] 是0 表示它的所有条目，相当于布尔值 false.

您可能想找出运行 sieve 函数的最佳位置。

Answer 2

你这里的增量有误：

for (int j = i * i; j <= n; j += i + i)

您需要将 j 增加 i，但实际上增加了 2*i。无论如何，我同意您从不调用 sieve.

之前的答案

找出一个数是否为质数

finding a number is prime or not

c++

primes