GCC Code Coverage Report

Directory: ./
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 100.0% 69 / 0 / 69
Functions: 100.0% 8 / 0 / 8
Branches: 96.0% 121 / 0 / 126
src/nt/is_prime/lib.hpp
Line Branch Exec Source
1 #pragma once
2
3 #include "../../math/mul_mod/lib.hpp"
4 #include "../../math/qpow/mod/lib.hpp"
5
6 namespace tifa_libs {
7
8 900372 CEXP bool is_prime(u64 n) NE {
9
2/2
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 900365 times.
 900372 retif_((n <= 2) [[unlikely]], n == 2);
10
2/2
✓ Branch 0 taken 255641 times.
✓ Branch 1 taken 644724 times.
 900365 if (~n & 1) return false;
11
4/4
✓ Branch 0 taken 588006 times.
✓ Branch 1 taken 56718 times.
✓ Branch 2 taken 434 times.
✓ Branch 3 taken 587572 times.
 644724 if (n < 8 || n == 61) return true;
12
6/6
✓ Branch 0 taken 481230 times.
✓ Branch 1 taken 106342 times.
✓ Branch 2 taken 412908 times.
✓ Branch 3 taken 68322 times.
✓ Branch 4 taken 23235 times.
✓ Branch 5 taken 389673 times.
 587572 if (!(n % 3) || !(n % 5) || !(n % 7)) return false;
13
2/2
✓ Branch 0 taken 20649 times.
✓ Branch 1 taken 369024 times.
 389673 if (n < 121) return true;
14 369024 auto f = [n, d = (n - 1) >> std::countr_zero(n - 1)](auto&& bases) NE -> bool {
15
14/14
bool tifa_libs::is_prime(unsigned long)::{lambda(auto:1&&)#1}::operator()<unsigned long const (&) [1]>(unsigned long const (&) [1]) const:
✓ Branch 0 taken 44518 times.
✓ Branch 1 taken 23812 times.
bool tifa_libs::is_prime(unsigned long)::{lambda(auto:1&&)#1}::operator()<unsigned long const (&) [2]>(unsigned long const (&) [2]) const:
✓ Branch 0 taken 60354 times.
✓ Branch 1 taken 16166 times.
bool tifa_libs::is_prime(unsigned long)::{lambda(auto:1&&)#1}::operator()<unsigned long const (&) [3]>(unsigned long const (&) [3]) const:
✓ Branch 0 taken 5596 times.
✓ Branch 1 taken 1366 times.
bool tifa_libs::is_prime(unsigned long)::{lambda(auto:1&&)#1}::operator()<unsigned long const (&) [4]>(unsigned long const (&) [4]) const:
✓ Branch 0 taken 3807 times.
✓ Branch 1 taken 599 times.
bool tifa_libs::is_prime(unsigned long)::{lambda(auto:1&&)#1}::operator()<unsigned long const (&) [5]>(unsigned long const (&) [5]) const:
✓ Branch 0 taken 14774 times.
✓ Branch 1 taken 1401 times.
bool tifa_libs::is_prime(unsigned long)::{lambda(auto:1&&)#1}::operator()<unsigned long const (&) [6]>(unsigned long const (&) [6]) const:
✓ Branch 0 taken 501857 times.
✓ Branch 1 taken 63346 times.
bool tifa_libs::is_prime(unsigned long)::{lambda(auto:1&&)#1}::operator()<unsigned long const (&) [7]>(unsigned long const (&) [7]) const:
✓ Branch 0 taken 346001 times.
✓ Branch 1 taken 44113 times.
 1127710 for (cu64 i : bases) {
16
9/14
bool tifa_libs::is_prime(unsigned long)::{lambda(auto:1&&)#1}::operator()<unsigned long const (&) [1]>(unsigned long const (&) [1]) const:
✓ Branch 0 taken 1 time.
✓ Branch 1 taken 44517 times.
bool tifa_libs::is_prime(unsigned long)::{lambda(auto:1&&)#1}::operator()<unsigned long const (&) [2]>(unsigned long const (&) [2]) const:
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 60350 times.
bool tifa_libs::is_prime(unsigned long)::{lambda(auto:1&&)#1}::operator()<unsigned long const (&) [3]>(unsigned long const (&) [3]) const:
✗ Branch 0 not taken.
✓ Branch 1 taken 5596 times.
bool tifa_libs::is_prime(unsigned long)::{lambda(auto:1&&)#1}::operator()<unsigned long const (&) [4]>(unsigned long const (&) [4]) const:
✗ Branch 0 not taken.
✓ Branch 1 taken 3807 times.
bool tifa_libs::is_prime(unsigned long)::{lambda(auto:1&&)#1}::operator()<unsigned long const (&) [5]>(unsigned long const (&) [5]) const:
✗ Branch 0 not taken.
✓ Branch 1 taken 14774 times.
bool tifa_libs::is_prime(unsigned long)::{lambda(auto:1&&)#1}::operator()<unsigned long const (&) [6]>(unsigned long const (&) [6]) const:
✗ Branch 0 not taken.
✓ Branch 1 taken 501857 times.
bool tifa_libs::is_prime(unsigned long)::{lambda(auto:1&&)#1}::operator()<unsigned long const (&) [7]>(unsigned long const (&) [7]) const:
✗ Branch 0 not taken.
✓ Branch 1 taken 346001 times.
 976907 if (!(i % n)) continue;
17 976902 u64 t = d, y = qpow_mod(i, t, n);
18
42/42
bool tifa_libs::is_prime(unsigned long)::{lambda(auto:1&&)#1}::operator()<unsigned long const (&) [1]>(unsigned long const (&) [1]) const:
✓ Branch 1 taken 87619 times.
✓ Branch 2 taken 20655 times.
✓ Branch 3 taken 80219 times.
✓ Branch 4 taken 7400 times.
✓ Branch 5 taken 63757 times.
✓ Branch 6 taken 16462 times.
bool tifa_libs::is_prime(unsigned long)::{lambda(auto:1&&)#1}::operator()<unsigned long const (&) [2]>(unsigned long const (&) [2]) const:
✓ Branch 1 taken 224538 times.
✓ Branch 2 taken 27719 times.
✓ Branch 3 taken 215401 times.
✓ Branch 4 taken 9137 times.
✓ Branch 5 taken 191907 times.
✓ Branch 6 taken 23494 times.
bool tifa_libs::is_prime(unsigned long)::{lambda(auto:1&&)#1}::operator()<unsigned long const (&) [3]>(unsigned long const (&) [3]) const:
✓ Branch 1 taken 12339 times.
✓ Branch 2 taken 1309 times.
✓ Branch 3 taken 10879 times.
✓ Branch 4 taken 1460 times.
✓ Branch 5 taken 8052 times.
✓ Branch 6 taken 2827 times.
bool tifa_libs::is_prime(unsigned long)::{lambda(auto:1&&)#1}::operator()<unsigned long const (&) [4]>(unsigned long const (&) [4]) const:
✓ Branch 1 taken 6877 times.
✓ Branch 2 taken 1368 times.
✓ Branch 3 taken 5879 times.
✓ Branch 4 taken 998 times.
✓ Branch 5 taken 4438 times.
✓ Branch 6 taken 1441 times.
bool tifa_libs::is_prime(unsigned long)::{lambda(auto:1&&)#1}::operator()<unsigned long const (&) [5]>(unsigned long const (&) [5]) const:
✓ Branch 1 taken 27020 times.
✓ Branch 2 taken 7708 times.
✓ Branch 3 taken 24651 times.
✓ Branch 4 taken 2369 times.
✓ Branch 5 taken 19954 times.
✓ Branch 6 taken 4697 times.
bool tifa_libs::is_prime(unsigned long)::{lambda(auto:1&&)#1}::operator()<unsigned long const (&) [6]>(unsigned long const (&) [6]) const:
✓ Branch 1 taken 873798 times.
✓ Branch 2 taken 121727 times.
✓ Branch 3 taken 749785 times.
✓ Branch 4 taken 124013 times.
✓ Branch 5 taken 493668 times.
✓ Branch 6 taken 256117 times.
bool tifa_libs::is_prime(unsigned long)::{lambda(auto:1&&)#1}::operator()<unsigned long const (&) [7]>(unsigned long const (&) [7]) const:
✓ Branch 1 taken 586853 times.
✓ Branch 2 taken 37103 times.
✓ Branch 3 taken 485861 times.
✓ Branch 4 taken 100992 times.
✓ Branch 5 taken 277955 times.
✓ Branch 6 taken 207906 times.
 2036633 while (t != n - 1 && y != 1 && y != n - 1) y = mul_mod_u(y, y, n), t *= 2;
19
28/28
bool tifa_libs::is_prime(unsigned long)::{lambda(auto:1&&)#1}::operator()<unsigned long const (&) [1]>(unsigned long const (&) [1]) const:
✓ Branch 0 taken 28055 times.
✓ Branch 1 taken 16462 times.
✓ Branch 2 taken 20706 times.
✓ Branch 3 taken 7349 times.
bool tifa_libs::is_prime(unsigned long)::{lambda(auto:1&&)#1}::operator()<unsigned long const (&) [2]>(unsigned long const (&) [2]) const:
✓ Branch 0 taken 36856 times.
✓ Branch 1 taken 23494 times.
✓ Branch 2 taken 28012 times.
✓ Branch 3 taken 8844 times.
bool tifa_libs::is_prime(unsigned long)::{lambda(auto:1&&)#1}::operator()<unsigned long const (&) [3]>(unsigned long const (&) [3]) const:
✓ Branch 0 taken 2769 times.
✓ Branch 1 taken 2827 times.
✓ Branch 2 taken 1481 times.
✓ Branch 3 taken 1288 times.
bool tifa_libs::is_prime(unsigned long)::{lambda(auto:1&&)#1}::operator()<unsigned long const (&) [4]>(unsigned long const (&) [4]) const:
✓ Branch 0 taken 2366 times.
✓ Branch 1 taken 1441 times.
✓ Branch 2 taken 1380 times.
✓ Branch 3 taken 986 times.
bool tifa_libs::is_prime(unsigned long)::{lambda(auto:1&&)#1}::operator()<unsigned long const (&) [5]>(unsigned long const (&) [5]) const:
✓ Branch 0 taken 10077 times.
✓ Branch 1 taken 4697 times.
✓ Branch 2 taken 7714 times.
✓ Branch 3 taken 2363 times.
bool tifa_libs::is_prime(unsigned long)::{lambda(auto:1&&)#1}::operator()<unsigned long const (&) [6]>(unsigned long const (&) [6]) const:
✓ Branch 0 taken 245740 times.
✓ Branch 1 taken 256117 times.
✓ Branch 2 taken 121733 times.
✓ Branch 3 taken 124007 times.
bool tifa_libs::is_prime(unsigned long)::{lambda(auto:1&&)#1}::operator()<unsigned long const (&) [7]>(unsigned long const (&) [7]) const:
✓ Branch 0 taken 138095 times.
✓ Branch 1 taken 207906 times.
✓ Branch 2 taken 37195 times.
✓ Branch 3 taken 100900 times.
 976902 if (y != n - 1 && (~t & 1)) return false;
20 }
21 150803 return true;
22 };
23 // NOLINTBEGIN(modernize-avoid-c-arrays)
24 369024 CEXP u64 THRES1 = 341531, BASE1[]{9345883071009581737u};
25 369024 CEXP u64 THRES2 = 1050535501, BASE2[]{336781006125, 9639812373923155};
26 369024 CEXP u64 THRES3 = 350269456337, BASE3[]{4230279247111683200, 14694767155120705706u, 16641139526367750375u};
27 369024 CEXP u64 THRES4 = 55245642489451, BASE4[]{2, 141889084524735, 1199124725622454117, 11096072698276303650u};
28 369024 CEXP u64 THRES5 = 7999252175582851, BASE5[]{2, 4130806001517, 149795463772692060, 186635894390467037, 3967304179347715805};
29 369024 CEXP u64 THRES6 = 585226005592931977, BASE6[]{2, 123635709730000, 9233062284813009, 43835965440333360, 761179012939631437, 1263739024124850375};
30 369024 CEXP u64 BASE7[]{2, 325, 9375, 28178, 450775, 9780504, 1795265022};
31 // NOLINTEND(modernize-avoid-c-arrays)
32
2/2
✓ Branch 0 taken 44518 times.
✓ Branch 1 taken 324506 times.
 369024 if (n < THRES1) return f(BASE1);
33
2/2
✓ Branch 0 taken 44178 times.
✓ Branch 1 taken 280328 times.
 324506 if (n < THRES2) return f(BASE2);
34
2/2
✓ Branch 0 taken 2847 times.
✓ Branch 1 taken 277481 times.
 280328 if (n < THRES3) return f(BASE3);
35
2/2
✓ Branch 0 taken 1979 times.
✓ Branch 1 taken 275502 times.
 277481 if (n < THRES4) return f(BASE4);
36
2/2
✓ Branch 0 taken 9115 times.
✓ Branch 1 taken 266387 times.
 275502 if (n < THRES5) return f(BASE5);
37
2/2
✓ Branch 0 taken 185079 times.
✓ Branch 1 taken 81308 times.
 266387 if (n < THRES6) return f(BASE6);
38 81308 return f(BASE7);
39 }
40
41 } // namespace tifa_libs
42