Code Coverage
 
Lines
Functions and Methods
Classes and Traits
Total
94.00% covered (success)
94.00%
47 / 50
80.00% covered (warning)
80.00%
4 / 5
 CRAP
0.00% covered (danger)
0.00%
0 / 1
Prime
94.00% covered (success)
94.00%
47 / 50
80.00% covered (warning)
80.00%
4 / 5
 26.15
0.00% covered (danger)
0.00%
0 / 1
 __construct
n/a
0 / 0
n/a
0 / 0
 1
 isMersenne
100.00% covered (success)
100.00%
2 / 2
100.00% covered (success)
100.00%
1 / 1
 1
 mersenne
100.00% covered (success)
100.00%
1 / 1
100.00% covered (success)
100.00%
1 / 1
 1
 rabinTest
88.89% covered (warning)
88.89%
24 / 27
0.00% covered (danger)
0.00%
0 / 1
 14.27
 sieveOfEratosthenes
100.00% covered (success)
100.00%
11 / 11
100.00% covered (success)
100.00%
1 / 1
 5
 isPrime
100.00% covered (success)
100.00%
9 / 9
100.00% covered (success)
100.00%
1 / 1
 4
1<?php
2/**
3 * Jingga
4 *
5 * PHP Version 8.1
6 *
7 * @package   phpOMS\Math\Number
8 * @copyright Dennis Eichhorn
9 * @license   OMS License 2.0
10 * @version   1.0.0
11 * @link      https://jingga.app
12 */
13declare(strict_types=1);
14
15namespace phpOMS\Math\Number;
16
17/**
18 * Well known functions class.
19 *
20 * @package phpOMS\Math\Number
21 * @license OMS License 2.0
22 * @link    https://jingga.app
23 * @since   1.0.0
24 */
25final class Prime
26{
27    /**
28     * Epsilon for float comparison.
29     *
30     * @var float
31     * @since 1.0.0
32     */
33    public const EPSILON = 4.88e-04;
34
35    /**
36     * Constructor.
37     *
38     * @since 1.0.0
39     * @codeCoverageIgnore
40     */
41    private function __construct()
42    {
43    }
44
45    /**
46     * Is mersenne number?
47     *
48     * @param int $n Number to test
49     *
50     * @return bool
51     *
52     * @since 1.0.0
53     */
54    public static function isMersenne(int $n) : bool
55    {
56        $mersenne = \log($n + 1, 2);
57
58        return $mersenne - (int) $mersenne < self::EPSILON;
59    }
60
61    /**
62     * Get mersenne number
63     *
64     * @param int $p Power
65     *
66     * @return int
67     *
68     * @since 1.0.0
69     */
70    public static function mersenne(int $p) : int
71    {
72        return (int) (2 ** $p) - 1;
73    }
74
75    /**
76     * Is prime?
77     *
78     * @param int $n Number to test
79     * @param int $k Accuracy
80     *
81     * @return bool
82     *
83     * @since 1.0.0
84     */
85    public static function rabinTest(int $n, int $k = 10000) : bool
86    {
87        if ($n === 2) {
88            return true;
89        }
90
91        if ($n < 2 || $n % 2 === 0) {
92            return false;
93        }
94
95        $d = $n - 1;
96        $s = 0;
97
98        while ($d % 2 === 0) {
99            $d /= 2;
100            ++$s;
101        }
102
103        for ($i = 0; $i < $k; ++$i) {
104            $a = \mt_rand(2, $n - 1);
105            $x = \bcpowmod((string) $a, (string) $d, (string) $n);
106
107            if ($x === false) {
108                return false;
109            }
110
111            if ($x == 1 || $x == $n - 1) {
112                continue;
113            }
114
115            for ($j = 1; $j < $s; ++$j) {
116                if ($x === null) {
117                    return false;
118                }
119
120                $mul = \bcmul($x, $x);
121                /*if ($mul === null) {
122                    return false;
123                }*/
124
125                $x = \bcmod($mul, (string) $n);
126                if ($x == 1 || $x === null) {
127                    return false;
128                }
129
130                if ($x == $n - 1) {
131                    continue 2;
132                }
133            }
134
135            return false;
136        }
137
138        return true;
139    }
140
141    /**
142     * Create prime numbers
143     *
144     * @param int $n Primes to generate
145     *
146     * @return int[]
147     *
148     * @since 1.0.0
149     */
150    public static function sieveOfEratosthenes(int $n) : array
151    {
152        $number = 2;
153        $range  = \range(2, $n);
154        $primes = \array_combine($range, $range);
155
156        if ($primes === false) {
157            return []; // @codeCoverageIgnore
158        }
159
160        while ($number * $number < $n) {
161            for ($i = $number; $i <= $n; $i += $number) {
162                if ($i === $number) {
163                    continue;
164                }
165
166                unset($primes[$i]);
167            }
168
169            $number = \next($primes);
170        }
171
172        return \array_values($primes);
173    }
174
175    /**
176     * Is prime?
177     *
178     * @param int $n Number to test
179     *
180     * @return bool
181     *
182     * @since 1.0.0
183     */
184    public static function isPrime(int $n) : bool
185    {
186        $i = 2;
187
188        if ($n === 2) {
189            return true;
190        }
191
192        $sqrtN = \sqrt($n);
193        while ($i <= $sqrtN) {
194            if ($n % $i === 0) {
195                return false;
196            }
197
198            ++$i;
199        }
200
201        return true;
202    }
203}