View Single Post
 2021-01-29, 13:57 #8 kruoli     "Oliver" Sep 2017 Porta Westfalica, DE 22×191 Posts Sieving itself should not be a problem. You should use primesieve if you are not eager to implement everything yourself: Code: $/usr/bin/time -v primesieve 2500000000000 Sieve size = 256 KiB Threads = 16 100% 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.