我怎样才能让这个函数输出最大数组值？

Question

我是 C++ 的新手，正在尝试使这段代码正常工作。这是一个基本算法质数。我制作了一个数组，其大小由用户输入定义。然后我需要打印只有这个数组中的最大质数。我怎么能在这里做到这一点？

unsigned long long nPrime(unsigned n) {
    long long *a = new long long[n + 1];
    long long maxNum = a[n];

    for (int i = 0; i < n + 1; i++) {
            a[i] = i;
    }
    for (int j = 2; j < n + 1; j++) {
        if (a[j] != 0) {
            for (int k = j * j; k < n + 1; k += j) {
                a[k] = 0;
            }
            cout << a[j] << endl;
        }
    }
    return 0;
}

Answer 1

您似乎在数组中用值 0 标记了非素数。我们知道素数都是正数，为简化起见，设maxNum为-1。然后我在函数的 and 处添加了一个 for ，它将计算数组中的最大质数。这是一种方法：

unsigned long long nPrime(unsigned n) {
    long long *a = new long long[n + 1];
    long long maxNum = -1;

    for (long long i = 0; i < n + 1; i++) {
        a[i] = i;
    }

    for (long long i = 2; i < n + 1; i++) {
        for (long long k = i * i; k < n + 1; k += i) {
            a[k] = 0;
        }
    }

    for (long long i = 1; i < n; i++) {
        if (a[i] != 0 && maxNum < a[i]) maxNum = a[i];
    }

    return maxNum;
}

另外，您可以使用更快的版本代替 last for。在此版本中，您甚至不需要 maxNum 值：让我们从末尾开始，第一个非零值将是答案：

for (long long i = n; i >= 2; i--) {
    if (a[i] != 0) return a[i];
}

Answer 2

您可以使用 std::max_element 从 <algorithm>:

中找到数组中最大的数字

return *std::max_element(a, a+n);

但这甚至没有必要。由于最大素数将是您找到的最后一个素数，因此只需跟踪它：

int biggestPrime = 2;

然后，当您找到素数时：

biggestPrime = j;

您还可以用 bool 数组替换 long long 数组，因为索引已经跟踪了数字：

unsigned long long nPrime(unsigned n) {
    bool *a = new bool[n + 1]();
    long long maxNum = a[n];
    int biggestPrime = 2;

    for (int j = 2; j < n + 1; j++) {
        if (!a[j]) {
            for (int k = j * j; k < n + 1; k += j) {
                a[k] = true;
            }
            biggestPrime = j;
        }
    }
    delete[] a;
    return biggestPrime;
}

最后但同样重要的是，完成后不要忘记 delete 动态分配的内存：

delete[] a;

我怎样才能让这个函数输出最大数组值？

How can I make this function output max array value?

c++

arrays

primes

max

data-structures