Mercurial > octave
comparison libinterp/corefcn/__isprimelarge__.cc @ 31051:5f015f2829b7
maint: Merge stable to default
| author | Arun Giridhar <arungiridhar@gmail.com> |
|---|---|
| date | Wed, 01 Jun 2022 17:20:22 -0400 |
| parents | b65e4c635343 3a93a77dd4cf |
| children | 068342cc93b8 |
comparison
equal
deleted
inserted
replaced
| 31049:d5997bbdb641 | 31051:5f015f2829b7 |
|---|---|
| 114 | 114 |
| 115 // Miller-Rabin test with the first 12 primes. | 115 // Miller-Rabin test with the first 12 primes. |
| 116 // If the number passes all 12 tests, then it is prime. | 116 // If the number passes all 12 tests, then it is prime. |
| 117 // If it fails any, then it is composite. | 117 // If it fails any, then it is composite. |
| 118 // The first 12 primes suffice to test all 64-bit integers. | 118 // The first 12 primes suffice to test all 64-bit integers. |
| 119 if (! millerrabin ( 2, d, r, n)) return false; | 119 return millerrabin ( 2, d, r, n) && millerrabin ( 3, d, r, n) |
| 120 if (! millerrabin ( 3, d, r, n)) return false; | 120 && millerrabin ( 5, d, r, n) && millerrabin ( 7, d, r, n) |
| 121 if (! millerrabin ( 5, d, r, n)) return false; | 121 && millerrabin (11, d, r, n) && millerrabin (13, d, r, n) |
| 122 if (! millerrabin ( 7, d, r, n)) return false; | 122 && millerrabin (17, d, r, n) && millerrabin (19, d, r, n) |
| 123 if (! millerrabin (11, d, r, n)) return false; | 123 && millerrabin (23, d, r, n) && millerrabin (29, d, r, n) |
| 124 if (! millerrabin (13, d, r, n)) return false; | 124 && millerrabin (31, d, r, n) && millerrabin (37, d, r, n); |
| 125 if (! millerrabin (17, d, r, n)) return false; | |
| 126 if (! millerrabin (19, d, r, n)) return false; | |
| 127 if (! millerrabin (23, d, r, n)) return false; | |
| 128 if (! millerrabin (29, d, r, n)) return false; | |
| 129 if (! millerrabin (31, d, r, n)) return false; | |
| 130 if (! millerrabin (37, d, r, n)) return false; | |
| 131 // If we are all the way here, then it is prime. | |
| 132 return true; | |
| 133 | 125 |
| 134 /* | 126 /* |
| 135 Mathematical references for the curious as to why we need only | 127 Mathematical references for the curious as to why we need only |
| 136 the 12 smallest primes for testing all 64-bit numbers: | 128 the 12 smallest primes for testing all 64-bit numbers: |
| 137 (1) https://oeis.org/A014233 | 129 (1) https://oeis.org/A014233 |