在前一百多个数上对拍
下面 fast_prime 只拿 2、3、5、7 去试除。把它和正确版在 2~120 上对拍一遍,数一数一致了几次:
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
bool ok_prime(int n) {
if (n < 2) return false;
for (int d = 2; d * d <= n; d++) {
if (n % d == 0) return false;
}
return true;
}
bool fast_prime(int n) {
// 只拿 2、3、5、7 试除——看起来又快又对
if (n < 2) return false;
for (int d : {2, 3, 5, 7}) {
if (n == d) return true;
if (n % d == 0) return false;
}
return true;
}
int main() {
int same = 0;
for (int n = 2; n <= 120; n++) {
if (fast_prime(n) == ok_prime(n)) same++;
}
cout << same << endl;
}
(本题用 g++ -std=c++17 -O0 编译。)
全部评论