(n: number)
| 82 | 5749, 5779, 5783, 5791, 5801, 5807, 5813, 5821, 5827, 5839, 5843, 5849, 5851, |
| 83 | 5857, 5861, 5867, 5869, 5879, 5881, 5897, 5903, 5923, 5927, 5939, 5953, 5981, |
| 84 | 5987, 6007, 6011, 6029, 6037, 6043, 6047, 6053, 6067, 6073, 6079, 6089, 6091, |
| 85 | 6101, 6113, 6121, 6131, 6133, 6143, 6151, 6163, 6173, 6197, 6199, 6203, 6211, |
| 86 | 6217, 6221, 6229, 6247, 6257, 6263, 6269, 6271, 6277, 6287, 6299, 6301, 6311, |
| 87 | 6317, 6323, 6329, 6337, 6343, 6353, 6359, 6361, 6367, 6373, 6379, 6389, 6397, |
| 88 | 6421, 6427, 6449, 6451, 6469, 6473, 6481, 6491, 6521, 6529, 6547, 6551, 6553, |
| 89 | 6563, 6569, 6571, 6577, 6581, 6599, 6607, 6619, 6637, 6653, 6659, 6661, 6673, |
| 90 | 6679, 6689, 6691, 6701, 6703, 6709, 6719, 6733, 6737, 6761, 6763, 6779, 6781, |
| 91 | 6791, 6793, 6803, 6823, 6827, 6829, 6833, 6841, 6857, 6863, 6869, 6871, 6883, |
| 92 | 6899, 6907, 6911, 6917, 6947, 6949, 6959, 6961, 6967, 6971, 6977, 6983, 6991, |
| 93 | 6997, 7001, 7013, 7019, 7027, 7039, 7043, 7057, 7069, 7079, 7103, 7109, 7121, |
| 94 | 7127, 7129, 7151, 7159, 7177, 7187, 7193, 7207, 7211, 7213, 7219, 7229, 7237, |
| 95 | 7243, 7247, 7253, 7283, 7297, 7307, 7309, 7321, 7331, 7333, 7349, 7351, 7369, |
| 96 | 7393, 7411, 7417, 7433, 7451, 7457, 7459, 7477, 7481, 7487, 7489, 7499, 7507, |
| 97 | 7517, 7523, 7529, 7537, 7541, 7547, 7549, 7559, 7561, 7573, 7577, 7583, 7589, |
| 98 | 7591, 7603, 7607, 7621, 7639, 7643, 7649, 7669, 7673, 7681, 7687, 7691, 7699, |
| 99 | 7703, 7717, 7723, 7727, 7741, 7753, 7757, 7759, 7789, 7793, 7817, 7823, 7829, |
| 100 | 7841, 7853, 7867, 7873, 7877, 7879, 7883, 7901, 7907, 7919, |
| 101 | ]); |
| 102 | |
| 103 | export const LARGEST_SMALL_PRIME = 7919; |
| 104 | |
| 105 | export function primeFactors( |
| 106 | n: number, |
| 107 | deadline?: number | DeadlineFrame |
| 108 | ): { [factor: number]: number } { |
| 109 | console.assert( |
| 110 | Number.isInteger(n) && n >= 0 && n < Number.MAX_SAFE_INTEGER, |
| 111 | n |
| 112 | ); |
| 113 | //https:rosettacode.org/wiki/Prime_decomposition#JavaScript |
| 114 | if (n <= 3) return { [n]: 1 }; |
| 115 | const result: { [factor: number]: number } = {}; |
| 116 | // Wheel factorization |
| 117 | let count = 0; |
| 118 | while (n % 2 === 0) { |
| 119 | count += 1; |
| 120 | n /= 2; |
| 121 | } |
| 122 | if (count > 0) result[2] = count; |
| 123 | count = 0; |
| 124 | while (n % 3 === 0) { |
| 125 | count += 1; |
| 126 | n /= 3; |
| 127 | } |
| 128 | if (count > 0) result[3] = count; |
| 129 | // @todo: could add more special cases: 5, 7, 11, 13 |
| 130 | let done = false; |
| 131 | while (!done) { |
| 132 | if (n === 1) return result; |
| 133 | // Beyond 2^32, trial division to √n is too slow (up to ~9·10⁷ candidates |
| 134 | // for a 2^53 input): switch to Miller–Rabin + Pollard rho. |
| 135 | if (n >= 2 ** 32) { |
| 136 | const sub = new Map<bigint, number>(); |
| 137 | factorWithRho(BigInt(n), sub, deadline); |
| 138 | for (const [p, e] of sub) { |
| 139 | const pn = Number(p); |
| 140 | result[pn] = (result[pn] ?? 0) + e; |
| 141 | } |
no test coverage detected