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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
|
#include "../util.h"
#define ll lll
#include <math/modPowIterativ.cpp>
#undef ll
#include <math/millerRabin.cpp>
bool naive(ll x) {
for (ll i = 2; i*i <= x; i++) {
if (x % i == 0) return false;
}
return x > 1;
}
ll mul(const map<ll, int>& facts) {
ll res = 1;
for (auto [p, c] : facts) {
for (int i = 0; i < c; i++) res *= p;
}
if (abs(res) > (1ll << 62)) cerr << "invalid number: " << res << FAIL;
return res;
}
void extra_tests() {
vector<map<ll, int>> test = {
{{-1, 1}, {1, 1}},
{{-2, 1}, {1, 1}},
{{-7, 1}, {1, 1}},
{{-19812365821, 1}, {1, 1}},
{}, // 1
{{2, 1}},
{{3, 1}},
{{2, 2}},
{{5, 1}},
{{2, 1}, {3, 1}},
{{2, 2}, {3, 1}},
{{2, 1}, {3, 2}},
{{2, 2}, {3, 2}},
{{2, 62}},
{{2, 18}, {5, 18}},
{{352523, 1}, {352817, 1}},
{{41, 1}, {71, 1}, {421, 1}, {811, 1}},
{{11, 1}, {17, 1}, {31, 1}, {61, 1}, {73, 1}, {66361, 1}},
{{500000003, 1}, {1999999973, 1}},
{{65537, 2}},
{{999665081, 1}, {999716071, 1}},
{{550177, 1}, {1100353, 1}, {1650529, 1}},
{{459397, 1}, {918793, 1}, {1378189, 1}},
{{37, 1}, {109, 1}},
{{31, 1}, {151, 1}},
{{239, 1}, {1429, 1}},
{{89, 1}, {1093, 1}},
{{2, 3}, {15800133918749317, 1}},
{{12251, 1}, {85751, 1}},
{{3, 1}, {5, 3}, {131, 1}, {6855593, 1}},
{{5, 1}, {1927962474784631, 1}},
{{197279, 1}, {1775503, 1}},
{{3716371, 1}, {14865481, 1}},
{{3, 1}, {5, 1}, {3075593, 1}, {3075593, 1}},
{{4880401, 1}, {9760801, 1}},
{{2822159, 1}, {11288633, 1}},
{{3290341, 1}, {6580681, 1}},
{{611557, 1}, {1834669, 1}},
{{9227, 1}, {894923, 1}, {968731, 1}},
{{3, 4}, {13, 1}, {62633, 2}},
{{2, 2}, {3, 1}, {5, 1}, {167, 2}, {299197, 2}},
{{332721269, 1}, {560937673, 1}},
{{30702523, 1}, {122810089, 1}},
{{24786439, 1}, {123932191, 1}},
{{382500329, 1}, {1530001313, 1}},
{{2, 4}, {5, 4}, {13, 1}, {30839, 2}},
{{3, 1}, {385417, 1}, {7985344259, 1}},
{{2, 4}, {3, 1}, {5, 1}, {7, 2}, {61, 1}, {179, 2}, {1381, 2}},
{{627838711, 1}, {1212379867, 1}},
{{3, 5}, {5, 3}, {41, 2}, {157321, 2}},
{{5, 2}, {13, 1}},
{{3, 1}, {5, 5}},
{{2, 1}, {73, 1}, {193, 1}},
{{5, 2}, {13, 1}, {19, 1}, {73, 1}},
{{2, 3}, {3, 1}, {407521, 1}},
{{2, 1}, {3, 1}, {299210837, 1}},
{{2, 8}, {3, 4}, {5, 2}, {7, 2}, {11, 1}, {13, 1}, {17, 1}, {19, 1}, {23, 1}, {29, 1}, {3137, 1}},
};
timer t;
for (auto factors : test) {
ll x = mul(factors);
t.start();
auto got = isPrime(x);
t.stop();
bool expected = sz(factors) == 1 && factors.begin()->second == 1;
if (got != expected) cerr << "error: " << x << FAIL;
}
if (t.time > 10) cerr << "too slow" << FAIL;
cerr << "stress tested: " << t.time << "ms" << endl;
}
void stress_test() {
ll work = 0;
for (ll i = 0; i < 10'000; i++) {
ll x = Random::integer<ll>(1, 1'000'000'000'000);
auto got = isPrime(x);
auto expected = naive(x);
if (got != expected) cerr << "error: " << x << FAIL;
work += sqrt(x);
}
cerr << "stress tested: " << work << endl;
}
constexpr int N = 200'000;
void performance_test() {
timer t;
hash_t hash = 0;
for (int operations = 0; operations < N; operations++) {
ll x = Random::integer<ll>(1e18 / 2, 1e18);
t.start();
hash += isPrime(x);
t.stop();
}
if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
}
int main() {
extra_tests();
stress_test();
performance_test();
}
|
