pku_oj: W11-01 最大素数问题（C++）

问题描述：

给定一个大于2的正整数N，要求输出小于N的最大素数。

分析：

1.要求小于N的最大素数，显然，解空间为 [2, N-1)

2.进一步缩小解空间，只有奇数才可能是素数，因此，只枚举[2, N-1)中的奇数

3.最后，采取从N-1到2的搜索次序，符合“最大素数”要求

基于上述三点，给出代码如下（C++语言描述）

#include <iostream>
bool Judge(int);
using namespace std;

int main()
{
    cout << "Please enter a positive integer N (greater than 2)：" << endl;
    int N;
    cin >> N;
    //input end
    int i;
    if (N % 2 == 0) {        //If N is even
        for (i = N - 1; i > 1; i = i - 2) {
            if (Judge(i)) {
                cout << i << endl;
                break;
            }
        }
    }
    else {            // N is odd
        for (i = N - 2; i > 1; i = i - 2) {
            if (Judge(i)) {
                cout << i << endl;
                break;
            }
        }
    }
    //Since 2 is an even number, the last special treatment
    if (i <= 1 && Judge(i)) 
            cout << "2" << endl;
    else if (i <= 1)
        cout << "no" << endl;;
    

    return 0;
}

bool Judge(int i)
{
    if (i < 2)
        return false;
    for (int j = 3; j*j <= i; j+=2) {
        if (i%j == 0)
            return false;
    }
    return true;
}

总结：

本题解法采用的“枚举”策略，现对枚举作简单小结

1.什么是枚举？

枚举是基于已有知识进行答案猜测的一种问题求解策略

2.枚举的思想是什么？

猜测。即从可能的集合中一一列举各元素。

3.两个注意点

a.猜测的结果必须是前面的猜测中没有出现过的.b.猜测的过程中要及早排除错误的答案

4.枚举的三个关键问题

a.给出解空间, 建立简洁的数学模型

b.减少搜索的空间

c.采用合适的搜索顺序

pku_oj: W11-01 最大素数问题 （C++）

推荐阅读

pku_oj: W11-01 最大素数问题（C++）