tzs • last Sunday at 11:20 PM

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