一·直接试除

bool is_prime3(unsigned long long n) { //slowfor (int i = 2; i < n - 1; i++) {if (n % i == 0) {return 0;}}return 1;
}

note：比较慢

二·一点优化

每次试除时其实只要除到 sqrt(n)

并且除2之外不需要试除偶数

bool is_prime2(unsigned long long n) { //middlelong long stop = sqrt(n) + 1;if (n == 2) {return 1;}if (n % 2 == 0) {return 0;}for (int i = 3; i <= stop; i += 2) {if (n % i == 0) {return 0;}}return 1;
}

三·6n ± 1

如果 n 是一个质数（不为2或3），那么：

n = 6n ± 1

因为如果 n 是一个质数（不为2或3）那么 n % 2 != 0 且 n % 3 != 0

bool is_prime(unsigned long long n) { //quickunsigned long long stop = n / 6 + 1, Tstop = sqrt(n) + 5;if (n == 2 || n == 3 || n == 5 || n == 7 || n == 11) {return 1;}if (n % 2 == 0 || n % 3 == 0 || n % 5 == 0 || n == 1) {return 0;}for (unsigned long long i = 1; i <= stop; i++) {if (i * 6 >= Tstop) {break;}if ((n % (i * 6 + 1) == 0) || (n % (i * 6 + 5) == 0)) {return 0;}}return 1;
}

四·测试

编写一个main()函数来测试一下：

int main() {unsigned long long n;int flag;clock_t start, end;while (true) {cout << "number: " << flush;cin >> n;cout << n << endl;bool tmp;start = clock();flag = is_prime3(n);end = clock();cout << flag  << "\t" << end - start << "ms\n";start = clock();tmp = is_prime2(n);end = clock();if (tmp != flag) {flag = -1;}cout << tmp << "\t" << end - start << "ms\n";start = clock();tmp = is_prime(n);end = clock();if (tmp != flag) {flag = -1;}cout << tmp << "\t" << end - start << "ms\n";switch(flag) {case -1:cout << "UNKNOW" << endl;break;case 0:cout << "NON-PRIME" << endl;break;case 1:cout << "PRIME" << endl;}}return 0;
}

五·完整代码：

#include <iostream>
#include <cmath>
#include <ctime>
using namespace std;bool is_prime3(unsigned long long n) { //slowfor (int i = 2; i < n - 1; i++) {if (n % i == 0) {return false;}}return true;
}bool is_prime2(unsigned long long n) { //unknowlong long stop = sqrt(n) + 1;if (n == 2) {return true;}if (n % 2 == 0) {return false;}for (int i = 3; i <= stop; i += 2) {if (n % i == 0) {return false;}}return true;
}bool is_prime(unsigned long long n) { //unknowlong long stop = n / 6 + 1, Tstop = sqrt(n) + 5;if (n == 2 || n == 3 || n == 5 || n == 7 || n == 11) {return true;}if (n % 2 == 0 || n % 3 == 0 || n % 5 == 0) {return false;}for (int i = 1; i <= stop; i++) {if (i * 6 >= Tstop) {break;}//cout << i*6+1 << "  " << i*6+5 << endl;if ((n % (i * 6 + 1) == 0) || (n % (i * 6 + 5) == 0)) {return false;}}return true;
}int main() {unsigned long long n;int flag;clock_t start, end;while (true) {cout << "number: " << flush;cin >> n;cout << n << endl;bool tmp;start = clock();flag = is_prime3(n);end = clock();cout << flag  << "\t" << end - start << "ms\n";start = clock();tmp = is_prime2(n);end = clock();if (tmp != flag) {flag = -1;}cout << tmp << "\t" << end - start << "ms\n";start = clock();tmp = is_prime(n);end = clock();if (tmp != flag) {flag = -1;}cout << tmp << "\t" << end - start << "ms\n";switch(flag) {case -1:cout << "UNKNOW" << endl;break;case 0:cout << "NON-PRIME" << endl;break;case 1:cout << "PRIME" << endl;}}return 0;
}