Math-Prime-Util icon indicating copy to clipboard operation
Math-Prime-Util copied to clipboard

`prime_count(a,b)` is slow for large `a` and `b`, with `|a-b|` small.

Open trizen opened this issue 1 year ago • 0 comments

For example, the following command takes about 10 seconds on my system:

time perl -Mntheory=:all -E 'use bigint; say prime_count(2**63 - 10, 2**63 + 1000)' 

However, getting the primes in the same range is very fast:

time perl -Mntheory=:all -E 'use bigint; say scalar @{primes(2**63 - 10, 2**63 + 1000)}'

Notice that for small enough a and b, the prime_count function is fast:

time perl -Mntheory=:all -E 'use bigint; say prime_count(2**50 - 10, 2**50 + 1000)'

trizen avatar Jun 22 '24 15:06 trizen