3 ms·

I think the problem comes when you do a multiplication and you need more primes for uniqueness.

• tzs 3mo ago
  I think you would probably just pick enough primes at the start to handle numbers up to the number of bits you need. If we stick with primes that fit in 32-bit unsigned integers, then using the largest k such primes covers numbers up this many bits or decimal digits: k bits digits 10 319 96 20 639 192 30 959 288 40 1279 385 50 1599 481 75 2399 722 100 3199 963 150 4799 1444 250 7999 2408 500 15999 4816 1000 31999 9632 Here it is if we use the k largest primes that fit in 16-bit unsigned integers: k bits digits 10 159 48 20 319 96 30 479 144 40 639 192 50 799 240 75 1199 361 100 1598 481 150 2397 721 250 3991 1201 500 7967 2398 1000 15868 4776 If we use primes that fit in 8-bit unsigned integers, here's what we can handle with the largest k such primes. This table only goes to 54 because after that we run out of primes. k bits digits 10 78 23 20 152 45 30 220 66 40 281 84 50 327 98 54 334 100
  • im3w1l 3mo ago
    This might work really well in practice idk, but I think it's not allowed by big O to pick a maximum supported size. Otherwise you could just make a lookup table. Your algorithm must be ready for anything.