费马定理 - GESP二级编程练习题

公元1640年，法国著名数学家费马发现：
2^1 + 1 = 3
2^2 + 1 = 5
2^4 + 1 = 17
2^8 + 1 = 257
2^16 + 1 = 65537
而3、5、17、257、65537都是质数，于是费马猜想：对于一切自然数n，2^n + 1都是质数，可是到了1732年，数学家欧拉发现一个数n并不满足费马的这个猜想，请问欧拉发现的这个数n最小是多少？（在long long的范围内）（7.2）

输入描述

无

输出描述

满足条件的数n

用例输入 1

用例输出 1

来源

需要找规律的循环内容：观察给出的例子，我们可以发现满足费马猜想的数n必须是一个素数。所以我们可以通过遍历自然数n并判断n+1是否为素数来找到满足条件的最小数。

具体实现如下：

#include <iostream>
using namespace std;
bool isPrime(int num) {
if (num <= 1) return false;
for (int i = 2; i * i <= num; i++) {
if (num % i == 0) return false;
}
return true;
}
int main() {
int n = 1;
while (true) {
if (isPrime(n + 1)) {
cout << n << endl;
break;
}
n++;
}
return 0;
}

时间复杂度分析：
对于每个n，我们需要判断n+1是否为素数，判断一个数是否为素数的时间复杂度为O(sqrt(n+1))。所以总的时间复杂度为O(n * sqrt(n))。

在给定的范围内，这个算法的时间复杂度是可以接受的。</