Indeed, the primes program uses Eratosthenes sieve using pre-calculated array of primes up to 65537, leading to possible errors (and, in this case real errors, as 65539 is also a prime) when range hits (65537+2)^2.
There are a few possible fixes, that I can think of:
a) don't support 64-bit numbers, set upper limit to UINT32_MAX
b) support 64-bit numbers, but set upper limit to (MAX(primes) + 2)**2 - 1
c) add some number of pre-calculated primes to array, and repeat b (supporting the whole 64-bit range would take 203280221 primes (which could be stored in a 4-byte uints, leading to ~800 megabytes of memory)
d) recursively use the sieve to prime itself to reach unlimited range (this adds computation time and algorithm complexity)
Indeed, the primes program uses Eratosthenes sieve using pre-calculated array of primes up to 65537, leading to possible errors (and, in this case real errors, as 65539 is also a prime) when range hits (65537+2)^2.
There are a few possible fixes, that I can think of:
a) don't support 64-bit numbers, set upper limit to UINT32_MAX
b) support 64-bit numbers, but set upper limit to (MAX(primes) + 2)**2 - 1
c) add some number of pre-calculated primes to array, and repeat b (supporting the whole 64-bit range would take 203280221 primes (which could be stored in a 4-byte uints, leading to ~800 megabytes of memory)
d) recursively use the sieve to prime itself to reach unlimited range (this adds computation time and algorithm complexity)