View Single Post
Old 2021-01-29, 13:57   #8
kruoli's Avatar
Sep 2017
Porta Westfalica, DE

33E16 Posts

Sieving itself should not be a problem. You should use primesieve if you are not eager to implement everything yourself:

$ /usr/bin/time -v primesieve 2500000000000
Sieve size = 256 KiB
Threads = 16
Seconds: 62.344
Primes: 90882915772
        Command being timed: "primesieve 2500000000000"
        User time (seconds): 992.74
        System time (seconds): 0.12
        Percent of CPU this job got: 1592%
        Elapsed (wall clock) time (h:mm:ss or m:ss): 1:02.35
        Average shared text size (kbytes): 0
        Average unshared data size (kbytes): 0
        Average stack size (kbytes): 0
        Average total size (kbytes): 0
        Maximum resident set size (kbytes): 47436
        Average resident set size (kbytes): 0
        Major (requiring I/O) page faults: 6
        Minor (reclaiming a frame) page faults: 15683
        Voluntary context switches: 210
        Involuntary context switches: 4092
        Swaps: 0
        File system inputs: 928
        File system outputs: 0
        Socket messages sent: 0
        Socket messages received: 0
        Signals delivered: 0
        Page size (bytes): 4096
        Exit status: 0
That's not even 50 MB. The space requirement for that command was in \(\mathcal{O}(\sqrt n)\). If you use the API of primesieve and do execute a command that is not only counting, it will of course take a bit longer, but not in a way that would cause delays.

So my next question would be: Do you really need to store the primes? According to your last thread and the paper, you will only use one prime at a time, in order. Only in the division step in the end, you use the primorial up to your largest used prime, and you do not need all primes stored for that. For an efficient implementation, you'd have to store in the order of [$]\mathcal{O}(\log p_\text{count})[/$] primes at any given time. The problem would be the result (divisor) getting large quickly.

Last fiddled with by kruoli on 2021-01-29 at 14:44 Reason: Being pedantic. Removed something I'm not yet sure about.
kruoli is offline   Reply With Quote