Fermat pseudoprimes: Difference between revisions
→{{header|Phix}}
(Added Wren) |
|||
Line 81:
</pre>
=={{header|Phix}}==
<!--<lang Phix>(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">fermat_pseudoprime</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: #000000;">base</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">is_prime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #004600;">false</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #004080;">mpz</span> <span style="color: #000000;">z</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">a</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(</span><span style="color: #000000;">base</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">mpz_powm_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">z</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">z</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #7060A8;">mpz_cmp_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">z</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;">0</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">limits</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">12000</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">25000</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">50000</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">100000</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;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">20</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</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;">nlx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">nl</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">limits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">first20</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{},</span> <span style="color: #000000;">counts</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: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">limits</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #000000;">limits</span><span style="color: #0000FF;">[$]</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">fermat_pseudoprime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">base</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">count</span><span style="color: #0000FF;"><</span><span style="color: #000000;">20</span> <span style="color: #008080;">then</span> <span style="color: #000000;">first20</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">x</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;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">=</span><span style="color: #000000;">nl</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">counts</span><span style="color: #0000FF;">[</span><span style="color: #000000;">nlx</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">count</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">nlx</span><span style="color: #0000FF;"><</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">limits</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">nlx</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #000000;">nl</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">limits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">nlx</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: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">shorten</span><span style="color: #0000FF;">(</span><span style="color: #000000;">first20</span><span style="color: #0000FF;">,</span><span style="color: #008000;">""</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%d"</span><span style="color: #0000FF;">),</span><span style="color: #008000;">","</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">columnize</span><span style="color: #0000FF;">({</span><span style="color: #000000;">limits</span><span style="color: #0000FF;">,</span><span style="color: #000000;">counts</span><span style="color: #0000FF;">}),</span><span style="color: #008000;">", "</span><span style="color: #0000FF;">,</span><span style="color: #000000;">fmt</span><span style="color: #0000FF;">:=</span><span style="color: #008000;">"%d:%5d"</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;">"Base %2d, counts to %s, first 20: %s\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">base</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</lang>-->
{{out}}
<pre>
Base 1, counts to 12000:10561, 25000:22237, 50000:44866, 100000:90407, first 20: 4,6,8,...,28,30,32
Base 2, counts to 12000: 25, 25000: 38, 50000: 55, 100000: 78, first 20: 341,561,645,...,6601,7957,8321
Base 3, counts to 12000: 25, 25000: 38, 50000: 53, 100000: 78, first 20: 91,121,286,...,4961,5551,6601
Base 4, counts to 12000: 50, 25000: 75, 50000: 111, 100000: 153, first 20: 15,85,91,...,1905,2047,2071
Base 5, counts to 12000: 22, 25000: 35, 50000: 54, 100000: 73, first 20: 4,124,217,...,8029,8911,9881
Base 6, counts to 12000: 31, 25000: 46, 50000: 74, 100000: 104, first 20: 35,185,217,...,4123,4495,5713
Base 7, counts to 12000: 21, 25000: 32, 50000: 49, 100000: 73, first 20: 6,25,325,...,10585,10621,11041
Base 8, counts to 12000: 76, 25000: 110, 50000: 150, 100000: 218, first 20: 9,21,45,...,651,861,949
Base 9, counts to 12000: 55, 25000: 83, 50000: 113, 100000: 164, first 20: 4,8,28,...,1036,1105,1288
Base 10, counts to 12000: 35, 25000: 53, 50000: 65, 100000: 90, first 20: 9,33,91,...,3367,4141,4187
Base 11, counts to 12000: 30, 25000: 41, 50000: 61, 100000: 89, first 20: 10,15,70,...,2821,4577,4921
Base 12, counts to 12000: 35, 25000: 60, 50000: 91, 100000: 127, first 20: 65,91,133,...,2233,2465,2701
Base 13, counts to 12000: 31, 25000: 51, 50000: 68, 100000: 91, first 20: 4,6,12,...,3605,5028,5149
Base 14, counts to 12000: 33, 25000: 51, 50000: 69, 100000: 96, first 20: 15,39,65,...,2665,2743,3277
Base 15, counts to 12000: 22, 25000: 31, 50000: 42, 100000: 70, first 20: 14,341,742,...,8701,8911,9073
Base 16, counts to 12000: 69, 25000: 102, 50000: 145, 100000: 200, first 20: 15,51,85,...,1387,1581,1687
Base 17, counts to 12000: 31, 25000: 44, 50000: 63, 100000: 83, first 20: 4,8,9,...,4005,4033,4187
Base 18, counts to 12000: 46, 25000: 69, 50000: 98, 100000: 134, first 20: 25,49,65,...,1649,1729,1921
Base 19, counts to 12000: 48, 25000: 70, 50000: 93, 100000: 121, first 20: 6,9,15,...,1661,1849,1891
Base 20, counts to 12000: 35, 25000: 49, 50000: 66, 100000: 101, first 20: 21,57,133,...,2821,2947,3059
</pre>
=={{header|Raku}}==
<lang perl6>use List::Divvy;
| |||