一、明确素数的定义

素数:只能被1和自己整除的数

二、写程序

1
2
3
4
5
6
def testFunc( i) :
    #需要判断这个数是否能被2以上i以下的数整除
    for j in range(2,i) :
        if i%j==0 :
            return False
    return True

三、检查特殊情况

当i为1或者2时不进行循环,直接跳出for,依旧满足需求,不需要修改

四、尝试使用其他语言写

1
2
3
4
5
6
7
bool testFunc(int i){
	for(int j=2;j<i;j++){
		if (i%j==0)
			return false;
	}
	return true;
}
1
2
3
4
5
6
7
8
public static boolean testFunc(int i) {
	for (int j = 2; j < i; j++) {
            if (i % j == 0) {
                return false;
            }
	}
	return true;
  }

五、思考高效率算法

当需要判断的值太大时,原算法效率很低,查阅资料得知一般使用 Miller-Rabin素性测试,但是无法百分百确定

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cmath>

// 快速幂取模
long long power(long long x, unsigned long long y, long long p) {
    long long res = 1; // 初始化结果

    x = x % p; // 取 x 对 p 的余数

    if (x == 0) return 0; // 如果 x 是 0，结果也是 0

    while (y > 0) {
        // 如果 y 是奇数，则乘以 x
        if (y % 2 == 1)
            res = (res * x) % p;

        // y 变为一半
        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}

// Miller-Rabin 素性测试
bool isPrime(unsigned long long n, int k) {
    // 处理 n - 1 = 2^r * d
    unsigned long long d = n - 1;
    int r = 0;
    while (d % 2 == 0) {
        d /= 2;
        r++;
    }

    // 进行 k 次测试
    for (int i = 0; i < k; i++) {
        // 随机选择一个在 [2, n-2] 范围内的整数
        unsigned long long a = 2 + rand() % (n - 3);

        // 计算 a^d % n
        unsigned long long x = power(a, d, n);

        if (x == 1 || x == n - 1)
            continue;

        // 重复 r - 1 次
        for (int j = 0; j < r - 1; j++) {
            x = (x * x) % n;
            if (x == n - 1)
                break;
        }

        // 如果都不等于 n - 1，则 n 不是素数
        if (x != n - 1)
            return false;
    }

    // 通过所有测试，n 可能是素数
    return true;
}

int main() {
    // 示例用法
    srand(static_cast<unsigned int>(time(nullptr))); // 为随机数生成器提供种子

    unsigned long long numberToCheck = 1125899906842597; // 你要检查的数字
    int k = 5; // 进行 5 次 Miller-Rabin 测试

    if (isPrime(numberToCheck, k)) {
        std::cout << numberToCheck << " 可能是素数。" << std::endl;
    } else {
        std::cout << numberToCheck << " 不是素数。" << std::endl;
    }

    return 0;
}