最大质数 题目描述 输入一个正整数 n ，找到 1 到 n 里最大的质数，如果没有质数则输出 No。 输入格式 输入一个正整数 n (n≤2×10 7 ) 。c++

题目要求你编写一个程序，输入一个正整数 n，你的任务是找出从 1 到 n 中的最大质数。如果在这个范围内找不到质数，你需要返回 "No"。质数是一个大于1的自然数，除了1和它本身以外不再有其他因子。

对于这种问题，你可以采用一种叫做“埃拉托斯特尼筛法”（Sieve of Eratosthenes）的经典算法来找寻一定范围内的所有质数。这个算法的基本思想是从2开始，将每个质数的倍数标记为合数，直到筛到 sqrt(n)。剩下的未被标记的数就是质数。

以下是C++的一种解决方案：

#include <iostream>
#include <vector>
using namespace std;

// Function to find prime number up to n
int largestPrime(int n) {
    vector<bool> isPrime(n+1, true);
    isPrime[0] = false;
    isPrime[1] = false;

    // Start from 2 and mark its multiples as composite
    for (int p = 2; p * p <= n; ++p) {
        if (isPrime[p]) {
            for (int i = p * p; i <= n; i += p)
                isPrime[i] = false;
        }
    }

    // Find the largest prime less than or equal to n
    int largest = -1;
    for (int i = n; i > 0 && isPrime[i]; --i) {
        largest = i;
    }

    return largest == -1 ? "No" : largest;
}

int main() {
    int n;
    cin >> n;
    cout << largestPrime(n) << endl;
    return 0;
}