Ormiston triples: Difference between revisions
Content added Content deleted
(→{{header|Go}}: marked incorrect) |
|||
Line 172: | Line 172: | ||
4,925 Ormiston triples before 10,000,000,000 |
4,925 Ormiston triples before 10,000,000,000 |
||
</pre> |
</pre> |
||
=={{header|Phix}}== |
|||
<!--<syntaxhighlight lang="phix">(phixonline)--> |
|||
<span style="color: #000080;font-style:italic;">-- |
|||
-- demo\rosetta\Ormiston_triplets.exw |
|||
-- ================================== |
|||
-- |
|||
-- Uses a segmented sieve, which is about half the speed of get_primes_le(), but uses far less memory. |
|||
-- If permited, get_primes_le(1e10) would generate a result of 455,052,511 primes, more than 32 bit |
|||
-- can cope with, and use over 6GB of ram, and take about 11mins 44s, that is on this box at least, |
|||
-- whereas this processes them on-the-fly, and only uses about 6MB of memory (ie 0.1% of 6GB). |
|||
--</span> |
|||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
|||
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span> |
|||
<span style="color: #008080;">procedure</span> <span style="color: #000000;">ormiston_triplets</span><span style="color: #0000FF;">(</span><span style="color: #004080;">atom</span> <span style="color: #000000;">limit</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #000080;font-style:italic;">// Generate primes using the segmented sieve of Eratosthenes. |
|||
// credit: https://gist.github.com/kimwalisch/3dc39786fab8d5b34fee</span> |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">segment_size</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">sqrt</span><span style="color: #0000FF;">(</span><span style="color: #000000;">limit</span><span style="color: #0000FF;">)),</span> |
|||
<span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">i</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">triplen</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span> |
|||
<span style="color: #004080;">atom</span> <span style="color: #000000;">p1</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">p2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">nc</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">min</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1e9</span><span style="color: #0000FF;">,</span><span style="color: #000000;">limit</span><span style="color: #0000FF;">),</span> <span style="color: #000000;">low</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">t1</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()+</span><span style="color: #000000;">1</span> |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">isprime</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #004600;">true</span><span style="color: #0000FF;">,</span><span style="color: #000000;">segment_size</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">),</span> |
|||
<span style="color: #000000;">primes</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{},</span> |
|||
<span style="color: #000000;">multiples</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{},</span> |
|||
<span style="color: #000000;">orm25</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">25</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">while</span> <span style="color: #000000;">low</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">limit</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">sieve</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #004600;">true</span><span style="color: #0000FF;">,</span><span style="color: #000000;">segment_size</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()></span><span style="color: #000000;">t1</span> <span style="color: #008080;">then</span> |
|||
<span style="color: #7060A8;">progress</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"Processing %,d/%,d (%3.2f%%)\r"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">low</span><span style="color: #0000FF;">,</span><span style="color: #000000;">limit</span><span style="color: #0000FF;">,(</span><span style="color: #000000;">low</span><span style="color: #0000FF;">/</span><span style="color: #000000;">limit</span><span style="color: #0000FF;">)*</span><span style="color: #000000;">100</span><span style="color: #0000FF;">})</span> |
|||
<span style="color: #000000;">t1</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()+</span><span style="color: #000000;">1</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #000080;font-style:italic;">// current segment = [low, high]</span> |
|||
<span style="color: #004080;">atom</span> <span style="color: #000000;">high</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">min</span><span style="color: #0000FF;">(</span><span style="color: #000000;">low</span><span style="color: #0000FF;">+</span><span style="color: #000000;">segment_size</span><span style="color: #0000FF;">,</span><span style="color: #000000;">limit</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #000080;font-style:italic;">// generate sieving primes using simple sieve of Eratosthenes</span> |
|||
<span style="color: #008080;">while</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">*</span><span style="color: #000000;">i</span><span style="color: #0000FF;"><=</span><span style="color: #7060A8;">min</span><span style="color: #0000FF;">(</span><span style="color: #000000;">high</span><span style="color: #0000FF;">,</span><span style="color: #000000;">segment_size</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">isprime</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">i</span><span style="color: #0000FF;">*</span><span style="color: #000000;">i</span> <span style="color: #008080;">to</span> <span style="color: #000000;">segment_size</span> <span style="color: #008080;">by</span> <span style="color: #000000;">i</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #000000;">isprime</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #000000;">i</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">2</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
|||
<span style="color: #000080;font-style:italic;">// initialize sieving primes for segmented sieve</span> |
|||
<span style="color: #008080;">while</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">*</span><span style="color: #000000;">s</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">high</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">isprime</span><span style="color: #0000FF;">[</span><span style="color: #000000;">s</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span> |
|||
<span style="color: #000000;">primes</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">s</span> |
|||
<span style="color: #000000;">multiples</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">*</span><span style="color: #000000;">s</span><span style="color: #0000FF;">-</span><span style="color: #000000;">low</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #000000;">s</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">2</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
|||
<span style="color: #000080;font-style:italic;">// sieve the current segment</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">mi</span><span style="color: #0000FF;">,</span><span style="color: #000000;">j</span> <span style="color: #008080;">in</span> <span style="color: #000000;">multiples</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">primes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">mi</span><span style="color: #0000FF;">]*</span><span style="color: #000000;">2</span> |
|||
<span style="color: #008080;">while</span> <span style="color: #000000;">j</span><span style="color: #0000FF;"><</span><span style="color: #000000;">segment_size</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #000000;">sieve</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span> |
|||
<span style="color: #000000;">j</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">k</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
|||
<span style="color: #000000;">multiples</span><span style="color: #0000FF;">[</span><span style="color: #000000;">mi</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">j</span> <span style="color: #0000FF;">-</span> <span style="color: #000000;">segment_size</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">while</span> <span style="color: #000000;">n</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">high</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">sieve</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">low</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span> <span style="color: #000080;font-style:italic;">// n is a prime</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">triplen</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #7060A8;">remainder</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">p1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">18</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">0</span> |
|||
<span style="color: #008080;">and</span> <span style="color: #7060A8;">sort</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">sprint</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p1</span><span style="color: #0000FF;">))=</span><span style="color: #7060A8;">sort</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">sprint</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">))</span> <span style="color: #008080;">then</span> |
|||
<span style="color: #000000;">p2</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span> |
|||
<span style="color: #000000;">triplen</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">2</span> |
|||
<span style="color: #008080;">else</span> |
|||
<span style="color: #000000;">p1</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #008080;">elsif</span> <span style="color: #000000;">triplen</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> |
|||
<span style="color: #008080;">and</span> <span style="color: #7060A8;">remainder</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">p2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">18</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">0</span> |
|||
<span style="color: #008080;">and</span> <span style="color: #7060A8;">sort</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">sprint</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p2</span><span style="color: #0000FF;">))=</span><span style="color: #7060A8;">sort</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">sprint</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">))</span> <span style="color: #008080;">then</span> |
|||
<span style="color: #000080;font-style:italic;">-- triplet found!</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">p1</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">nc</span> <span style="color: #008080;">then</span> |
|||
<span style="color: #004080;">string</span> <span style="color: #000000;">e</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">elapsed_short</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #7060A8;">progress</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"%,d Ormiston triplets before %,d (%s)\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">count</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">nc</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">e</span><span style="color: #0000FF;">})</span> |
|||
<span style="color: #000000;">nc</span> <span style="color: #0000FF;">*=</span> <span style="color: #000000;">10</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #000000;">count</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">count</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">25</span> <span style="color: #008080;">then</span> |
|||
<span style="color: #000000;">orm25</span><span style="color: #0000FF;">[</span><span style="color: #000000;">count</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"%d"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">p1</span><span style="color: #0000FF;">})</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">count</span><span style="color: #0000FF;">=</span><span style="color: #000000;">25</span> <span style="color: #008080;">then</span> |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Smallest members of first 25 Ormiston triplets:\n%s\n"</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">join_by</span><span style="color: #0000FF;">(</span><span style="color: #000000;">orm25</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">))</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #000080;font-style:italic;">-- overlapping (and leave triplen set to 2):</span> |
|||
<span style="color: #000000;">p1</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">p2</span> |
|||
<span style="color: #000000;">p2</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span> |
|||
<span style="color: #000080;font-style:italic;">-- (for disjoint-only just set triplen to 0)</span> |
|||
<span style="color: #008080;">else</span> |
|||
<span style="color: #000000;">p1</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span> |
|||
<span style="color: #000000;">triplen</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #000000;">n</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">2</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
|||
<span style="color: #000000;">low</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">segment_size</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
|||
<span style="color: #004080;">string</span> <span style="color: #000000;">e</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">elapsed_short</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #7060A8;">progress</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"%,d Ormiston triplets before %,d (%s)\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">count</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">nc</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">e</span><span style="color: #0000FF;">})</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span> |
|||
<span style="color: #000000;">ormiston_triplets</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">iff</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">platform</span><span style="color: #0000FF;">()=</span><span style="color: #004600;">JS</span><span style="color: #0000FF;">?</span><span style="color: #000000;">1e8</span><span style="color: #0000FF;">:</span><span style="color: #000000;">1e9</span><span style="color: #0000FF;">))</span> |
|||
<!--</syntaxhighlight>--> |
|||
{{out}} |
|||
With limit upped to 1e10 |
|||
<pre> |
|||
Smallest members of first 25 Ormiston triplets: |
|||
11117123 12980783 14964017 32638213 32964341 |
|||
33539783 35868013 44058013 46103237 48015013 |
|||
50324237 52402783 58005239 60601237 61395239 |
|||
74699789 76012879 78163123 80905879 81966341 |
|||
82324237 82523017 83279783 86050781 92514341 |
|||
368 Ormiston triplets before 1,000,000,000 (56s) |
|||
4,925 Ormiston triplets before 10,000,000,000 (21:32) |
|||
</pre> |
|||
Note that running this under pwa/p2js shows 25<1e8 in 8s, a limit of 1e9 would get you a blank screen for 1min 25s<br> |
|||
I have not the patience to see whether JavaScript would actually cope with 1e10, but it should. |
|||
=={{header|Wren}}== |
=={{header|Wren}}== |