Rosetta Code

Ramanujan primes: Difference between revisions

Page Discussion

Ramanujan primes (view source)

Revision as of 06:16, 10 September 2021

4,172 bytes added ,  2 years ago
→‎{{header|Phix}}: replaced with faster version
(→‎{{header|Go}}: Replace existing solution with a much faster one.)
(→‎{{header|Phix}}: replaced with faster version)
Line 481:
 
=={{header|Phix}}==
{{trans|JuliaGo}}
{{libheader|Phix/online}}
You can run this online [http://phix.x10.mx/p2js/Ramanujan_primes.htm here].
<!--<lang Phix>(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #004080;">atomsequence</span> <span style="color: #000000;">t0pi</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">(){}</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">picache</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>▼
<span style="color: #008080;">functionprocedure</span> <span style="color: #000000;">piprimeCounter</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">nlimit</span><span style="color: #0000FF;">)</span>
<span style="color: #008080000000;">ifpi</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span> <span style="color: #0000007060A8;">0repeat</span> <span style="color: #0080800000FF;">then(</span> <span style="color: #008080000000;">return1</span> <span style="color: #0000000000FF;">0,</span> <span style="color: #008080000000;">endlimit</span> <span style="color: #0080800000FF;">if)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">nlimit</span> <span style="color: #0000FF;">></span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">picache</span><span style="color: #0000FF;">)1</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">primespi</span> <span style="color: #0000FF;">=[</span> <span style="color: #7060A8000000;">get_primes_le1</span><span style="color: #0000FF;">(]</span> <span style="color: #0000000000FF;">n=</span> <span style="color: #0000FF000000;">)0</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #7060A8000000;">length4</span><span style="color: #0000FF;">(</span><span style="color: #000000008080;">picacheto</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1limit</span> <span style="color: #008080;">toby</span> <span style="color: #000000;">n2</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">kpi</span> <span style="color: #0000FF;">=[</span> <span style="color: #7060A8000000;">binary_searchi</span><span style="color: #0000FF;">(]</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,=</span> <span style="color: #000000;">primes</span><span style="color: #0000FF;">)0</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">k</span><span style="color: #0000FF;"><</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">=-</span><span style="color: #000000;">k</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: #004080;">integer</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">picachesq</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">k9</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">sq</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">limit</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">pi</span><span style="color: #0000FF;">[</span><span style="color: #000000;">p</span><span style="color: #0000FF;">]!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
▲ <span style="color: #008080;">iffor</span> <span style="color: #000000;">kq</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">0sq</span> <span style="color: #008080;">thento</span> <span style="color: #000000;">klimit</span> <span style="color: #0000FF008080;">=-by</span> <span style="color: #000000;">kp</span><span style="color: #0000FF;">-*</span><span style="color: #000000;">1</span> <span style="color: #008080;">end2</span> <span style="color: #008080;">ifdo</span>
<span style="color: #000000;">pi</span><span style="color: #0000FF;">[</span><span style="color: #000000;">q</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</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;">sq</span> <span style="color: #0000FF;">+=</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">p</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">)*</span><span style="color: #000000;">4</span>
<span style="color: #000000;">p</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: #004080;">sequenceatom</span> <span style="color: #000000;">picachetotal</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF000000;">{}0</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #000000;">limit</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">total</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">pi</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">pi</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">total</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: #008080;">returnend</span> <span style="color: #000000;">picache</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF008080;">]procedure</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">ramanujanMax</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">4</span><span style="color: #0000FF;">*</span><span style="color: #000000;">n</span><span style="color: #0000FF;">*</span><span style="color: #7060A8;">log</span><span style="color: #0000FF;">(</span><span style="color: #000000;">4</span><span style="color: #0000FF;">*</span><span style="color: #000000;">n</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">Ramanujan_primeramanujanPrime</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #004080008080;">integerif</span> <span style="color: #000000;">maxpossn</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">ceil</span><span style="color: #0000FF;">(</span><span style="color: #000000;">41</span><span style="color: #0000FF;">*</span><span style="color: #000000008080;">nthen</span><span style="color: #0000FF;">*(</span><span style="color: #7060A8008080;">logreturn</span><span style="color: #0000FF;">(</span><span style="color: #000000;">42</span><span style="color: #0000FF;">*</span><span style="color: #000000008080;">nend</span><span style="color: #0000FF;">)/</span><span style="color: #7060A8;">log</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2</span><span style="color: #0000FF008080;">))))if</span>
<span style="color: #008080004080;">forinteger</span> <span style="color: #000000;">imaxposs</span> <span style="color: #0000FF;">=</span><span style="color: #000000;">maxposs</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1ramanujanMax</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-(</span><span style="color: #000000;">1n</span> <span style="color: #0080800000FF;">do)</span>
<span style="color: #008080;">iffor</span> <span style="color: #000000;">pii</span><span style="color: #0000FF;">(=</span><span style="color: #000000;">imaxposs</span><span style="color: #0000FF;">)</span> <span style="color: #0000FF;">-</span> <span style="color: #0000007060A8;">piodd</span><span style="color: #0000FF;">(</span><span style="color: #7060A8000000;">floormaxposs</span><span style="color: #0000FF;">()</span> <span style="color: #000000008080;">ito</span><span style="color: #0000FF;">/</span><span style="color: #000000;">21</span> <span style="color: #0000FF008080;">))by</span> <span style="color: #0000FF;"><-</span> <span style="color: #000000;">n2</span> <span style="color: #008080;">thendo</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">pi</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]-</span><span style="color: #000000;">pi</span><span style="color: #0000FF;">[</span><span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)]</span> <span style="color: #0000FF;"><</span> <span style="color: #000000;">n</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">i</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
Line 511 ⟶ 528:
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #004080;">sequenceatom</span> <span style="color: #000000;">rt0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">applytime</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">100</span><span style="color: #0000FF;">),</span><span style="color: #000000;">Ramanujan_prime</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">lim</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">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;">5</span><span style="color: #0000FF;">:</span><span style="color: #000000;">6</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">primeCounter</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ramanujanMax</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">lim</span><span style="color: #0000FF;">)))</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">apply</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">100</span><span style="color: #0000FF;">),</span><span style="color: #000000;">ramanujanPrime</span><span style="color: #0000FF;">)</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;">"%s\n"</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">join_by</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">apply</span><span style="color: #0000FF;">(</span><span style="color: #004600;">true</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">,{{</span><span style="color: #008000;">"%5d"</span><span style="color: #0000FF;">},</span><span style="color: #000000;">r</span><span style="color: #0000FF;">}),</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">20</span><span style="color: #0000FF;">,</span><span style="color: #008000;">""</span><span style="color: #0000FF;">))</span>
<span style="color: #7060A8008080;">printffor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1p</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"The 1000th Ramanujan prime is %d\n"</span><span style="color: #0000FF000000;">,3</span> <span style="color: #000000008080;">Ramanujan_primeto</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1000lim</span> <span style="color: #0000FF008080;">))do</span>
<span style="color: #7060A8;">printf</span> <span style="color: #0000FF004080;">(integer</span> <span style="color: #000000;">1n</span> <span style="color: #0000FF;">,=</span> <span style="color: #0080007060A8;">"The 10,000th Ramanujan prime is %d\n"power</span><span style="color: #0000FF;">,(</span> <span style="color: #000000;">Ramanujan_prime10</span><span style="color: #0000FF;">(,</span><span style="color: #000000;">10000p</span><span style="color: #0000FF;">))</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">?(</span><span style="color: #7060A8000000;">elapsed1</span><span style="color: #0000FF;">(,</span><span style="color: #7060A8008000;">time"The %,dth Ramanujan prime is %,d\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ramanujanPrime</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0n</span><span style="color: #0000FF;">)})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</lang>-->
{{out}}
Line 525 ⟶ 546:
1087 1091 1097 1103 1151 1163 1187 1217 1229 1249 1277 1289 1297 1301 1367 1373 1423 1427 1429 1439
 
The 1000th1,000th Ramanujan prime is 1940319,403
The 10,000th Ramanujan prime is 242057242,057
The 100,000th Ramanujan prime is 2,916,539
"0.6s"▼
The 1,000,000th Ramanujan prime is 34,072,993
▲"02.6s7s"
</pre>
<small>The last line is omitted under pwa/p2js since the primeCounter array is too much for Javascript to handle.</small>
 
=={{header|Raku}}==
Petelomax
7,805

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/315652"