Rosetta Code

Multi-base primes: Difference between revisions

Page Discussion

Multi-base primes (view source)

Revision as of 17:13, 3 July 2021

5,816 bytes added ,  2 years ago
→‎{{header|Phix}}: improved range checking, at some cost to performance
(Added C++ solution)
(→‎{{header|Phix}}: improved range checking, at some cost to performance)
Line 292:
 
=={{header|Phix}}==
Originally translated from Rust, but changed to a much fuller range of digits, as per talk page.
<!--<lang Phix>(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">digs</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: #000000;">ndig</span><span style="color: #0000FF;">)</span>▼
<span style="color: #004080;">sequence</span> <span style="color: #000000;">digits</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;">ndig</span><span style="color: #0000FF;">)</span>▼
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">digits</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>▼
<span style="color: #000000;">digits</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: #7060A8;">remainder</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)</span>▼
<span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">/</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)</span>▼
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>▼
<span style="color: #008080;">return</span> <span style="color: #000000;">digits</span>▼
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>▼
<span style="color: #008080;">function</span> <span style="color: #000000;">evalpoly</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">result</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)1</span> <span style="color: #008080;">to</span> <span style="color: #0000007060A8;">1length</span> <span style="color: #0080800000FF;">by(</span> <span style="color: #0000FF000000;">-p</span><span style="color: #0000000000FF;">1)</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">result</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">result</span><span style="color: #0000FF;">*</span><span style="color: #000000;">x</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">y</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">result</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">stringify</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">digits</span><span style="color: #0000FF;">)</span>
▲ <span style="color: #000000004080;">digitsstring</span> <span style="color: #0000FF000000;">[res</span> <span style="color: #0000000000FF;">i=</span> <span style="color: #0000FF7060A8;">]repeat</span> <span style="color: #0000FF;">=(</span> <span style="color: #7060A8008000;">remainder'0'</span><span style="color: #0000FF;">(,</span><span style="color: #0000007060A8;">nlength</span><span style="color: #0000FF;">,(</span><span style="color: #000000;">10digits</span><span style="color: #0000FF;">))</span>
▲ <span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">digits</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">di</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">res</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;">di</span> <span style="color: #0000FF;">+</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">di</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">9</span><span style="color: #0000FF;">?</span><span style="color: #008000;">'0'</span><span style="color: #0000FF;">:</span><span style="color: #008000;">'a'</span><span style="color: #0000FF;">-</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)</span>
▲ <span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
▲ <span style="color: #008080;">return</span> <span style="color: #000000;">digitsres</span>
▲ <span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">max_prime_bases</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">ndig</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">maxbase</span><span style="color: #0000FF;">)</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: #004080000000;">sequencet1</span> <span style="color: #0000000000FF;">maxprimebases=</span> <span style="color: #0000FF7060A8;">=time</span> <span style="color: #0000FF;">{}()+</span><span style="color: #000000;">1</span>
<span style="color: #004080;">integersequence</span> <span style="color: #000000;">maxlenmaxprimebases</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">{},</span> <span style="color: #000000;">limit</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;">ndig</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span> <span style="color: #000000;">limitdigits</span> <span style="color: #0000FF;">/=</span> <span style="color: #0000007060A8;">10repeat</span> <span style="color: #0080800000FF;">to(</span> <span style="color: #000000;">limit0</span><span style="color: #0000FF;">-,</span><span style="color: #000000;">1ndig</span> <span style="color: #0080800000FF;">do)</span>
<span style="color: #004080;">sequenceinteger</span> <span style="color: #000000;">digitsmaxlen</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">digs</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ndig</span><span style="color: #0000FF;">),</span> <span style="color: #000000;">bases</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">baselimit</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">maxpower</span><span style="color: #0000FF;">(</span><span style="color: #000000;">digits10</span><span style="color: #0000FF;">)+,</span><span style="color: #000000;">1ndig</span> <span style="color: #0080800000FF;">to</span> <span style="color: #000000;">maxbase</span> <span style="color: #008080;">do),</span>
<span style="color: #000000;">maxdigit</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">maxbase</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">ndig</span><span style="color: #0000FF;">></span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> <span style="color: #000000;">digits</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: #000000;">1</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">digits</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
▲ <span style="color: #008080004080;">functioninteger</span> <span style="color: #000000;">digsdi</span> <span style="color: #0000FF;">(=</span> <span style="color: #004080000000;">integerdigits</span> <span style="color: #0000000000FF;">n[</span><span style="color: #0000FF000000;">,i</span> <span style="color: #0000000000FF;">ndig]+</span><span style="color: #0000FF000000;">)1</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">di</span><span style="color: #0000FF;"><</span><span style="color: #000000;">maxdigit</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">digits</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;">di</span>
<span style="color: #008080;">exit</span>
<span style="color: #008080;">else</span>
<span style="color: #000000;">di</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #000000;">digits</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;">0</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
▲ <span style="color: #004080;">sequenceinteger</span> <span style="color: #000000;">digitsminbase</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeatmax</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0digits</span><span style="color: #0000FF;">,)+</span><span style="color: #000000;">ndig1</span><span style="color: #0000FF;">),</span>
▲ <span style="color: #000000;">nmaxposs</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8000000;">floormaxbase</span><span style="color: #0000FF;">(-</span><span style="color: #000000;">nminbase</span><span style="color: #0000FF;">/+</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)1</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">minbase</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #000080;font-style:italic;">-- (ie we just wrapped round to all 0s)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">bases</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">base</span><span style="color: #0000FF;">=</span><span style="color: #000000;">minbase</span> <span style="color: #008080;">to</span> <span style="color: #000000;">maxbase</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">is_prime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">evalpoly</span><span style="color: #0000FF;">(</span><span style="color: #000000;">base</span><span style="color: #0000FF;">,</span><span style="color: #000000;">digits</span><span style="color: #0000FF;">))</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">bases</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">base</span>
<span style="color: #008080;">else</span>
<span style="color: #000000;">maxposs</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">maxposs</span><span style="color: #0000FF;"><</span><span style="color: #000000;">maxlen</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #000080;font-style:italic;">-- (a 5-fold speedup)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
Line 325 ⟶ 348:
<span style="color: #008080;">if</span> <span style="color: #000000;">l</span><span style="color: #0000FF;">></span><span style="color: #000000;">maxlen</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">maxlen</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">l</span>
<span style="color: #000000;">maxdigit</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">maxbase</span><span style="color: #0000FF;">-</span><span style="color: #000000;">maxlen</span> <span style="color: #000080;font-style:italic;">-- (around 20-fold speedup)</span>
<span style="color: #000000;">maxprimebases</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">l</span><span style="color: #0000FF;">=</span><span style="color: #000000;">maxlen</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">maxprimebases</span> <span style="color: #0000FF;">&=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">nstringify</span><span style="color: #0000FF;">(</span><span style="color: #000000;">digits</span><span style="color: #0000FF;">),</span> <span style="color: #000000;">bases</span><span style="color: #0000FF;">}}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">endif</span> <span style="color: #7060A8;">platform</span><span style="color: #0000FF;">()!=</span><span style="color: #004600;">JS</span> <span style="color: #008080;">and</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()></span><span style="color: #000000;">t1</span> <span style="color: #008080;">forthen</span>
<span style="color: #7060A8;">progress</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"%V\r"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">digits</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: #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</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;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%d character numeric strings that are prime in %d bases (%s):\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">ndig</span><span style="color: #0000FF;">,</span><span style="color: #000000;">maxlen</span><span style="color: #0000FF;">,</span><span style="color: #000000;">e</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">maxprimebases</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</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;">" %ds =&gt; %V\n"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">maxprimebases</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</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;">"\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</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;">54</span><span style="color: #0000FF;">:</span><span style="color: #000000;">6</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">max_prime_bases</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">36</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
Line 356 ⟶ 384:
737 => {8,9,11,12,13,15,16,17,19,22,23,24,25,26,29,30,31,36}
 
4 character numeric strings that are prime in 19 bases (0.3s6s):
1727 => {8,9,11,12,13,15,16,17,19,20,22,23,24,26,27,29,31,33,36}
5347 => {8,9,10,11,12,13,16,18,19,22,24,25,26,30,31,32,33,34,36}
 
5 character numeric strings that are prime in 18 bases (418.9s6s):
30271 => {8,10,12,13,16,17,18,20,21,23,24,25,31,32,33,34,35,36}
 
6 character numeric strings that are prime in 18 bases (111 minuteminutes and 59s17s):
441431 => {5,8,9,11,12,14,16,17,19,21,22,23,26,28,30,31,32,33}
</pre>
<small>As usual we skip the last entrycouple of entries under pwa/p2js to avoid staring at a blank screen for ages</small>
 
=={{header|Raku}}==
Petelomax
7,805

edits

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