Rosetta Code

Home primes: Difference between revisions

Page Discussion

Home primes (view source)

Revision as of 05:15, 21 June 2021

2,602 bytes removed ,  2 years ago
→‎{{header|Phix}}: added a new mpz_pollard_rho() routine.
(Add J)
(→‎{{header|Phix}}: added a new mpz_pollard_rho() routine.)
Line 357:
 
=={{header|Phix}}==
Added a new mpz_pollard_rho routine, based on the [[wp:Pollard%27s_rho_algorithm]] C code.
No stretch goal here this time, just the basic task. Note that mpz_prime_factors() needs a maxprime of 12207 or more to cover the 130517 needed for HP8, and in fact the 20000 used below was found by doubling a failing 10000, which...
<!--<lang Phix>(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #0000007060A8;">lastprequires</span> <span style="color: #0000FF;">=(</span> <span style="color: #008000;">"_1.0.0"</span><span style="color: #0000FF;">&</span><span style="color: #000000;">lastp)</span>▼
<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span>
Line 365 ⟶ 366:
<span style="color: #004080;">string</span> <span style="color: #000000;">s</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;">n</span><span style="color: #0000FF;">),</span> <span style="color: #000000;">lastp</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">s</span><span style="color: #0000FF;">}</span>
<span style="color: #008080004080;">elsifatom</span> <span style="color: #7060A8000000;">lengtht0</span> <span style="color: #0000FF;">(=</span> <span style="color: #0000007060A8;">rrtime</span><span style="color: #0000FF;">()=</span><span style="color: #000000;">1</span> ▼
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">substitute</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"_"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">""</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">rr</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_prime_factorsmpz_pollard_rho</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #000000004600;">20000true</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rr</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: #000000;">lastps</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rr</span><span style="color: #0000FF;">[$][,</span><span style="color: #000000008000;">1"_"</span><span style="color: #0000FF;">])</span>
<span style="color: #000000;">res</span> <span style="color: #0040800000FF;">mpz=</span> <span style="color: #0000007060A8;">pappend</span> <span style="color: #0000FF;">=(</span> <span style="color: #7060A8000000;">mpz_initres</span><span style="color: #0000FF;">(,</span><span style="color: #000000;">lastps</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #7060A8;">mpz_prime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)</span>▼
<span style="color: #008080;">or</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rr</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: #000000;">rr</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rr</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..$-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
▲ <span style="color: #000000;">lastp</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"_"</span><span style="color: #0000FF;">&</span><span style="color: #000000;">lastp</span>
▲ <span style="color: #008080;">elsif</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rr</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">1</span>
<span style="color: #008080;">and</span> <span style="color: #000000;">rr</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">][</span><span style="color: #000000;">2</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: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""</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;">rr</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">atom</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">prime</span><span style="color: #0000FF;">,</span><span style="color: #000000;">pow</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rr</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">si</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;">prime</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">pow</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">s</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">si</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">lastp</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">s</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">lastp</span>
<span style="color: #000000;">lastp</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">..$])</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
▲ <span style="color: #008080004080;">ifatom</span> <span style="color: #008080000000;">nott</span> <span style="color: #7060A80000FF;">mpz_prime=</span> <span style="color: #0000FF7060A8;">(time</span><span style="color: #0000000000FF;">p()-</span><span style="color: #0000FF000000;">)t0</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">niter</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)-</span><span style="color: #000000;">1</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">iter</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">niter</span><span style="color: #0000FF;">></span><span style="color: #000000;">1</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;">niter</span><span style="color: #0000FF;">):</span><span style="color: #008000;">""</span><span style="color: #0000FF;">),</span>
▲ <span style="color: #000000;">e</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">andiff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rrt</span><span style="color: #0000FF;">[></span><span style="color: #000000;">0.1</span><span style="color: #0000FF;">]?</span><span style="color: #008000;">" ["</span><span style="color: #0000FF;">&</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2t</span><span style="color: #0000FF;">])&</span><span style="color: #008000;">"]"</span><span style="color: #0000000000FF;">1:</span><span style="color: #008000;">""</span><span style="color: #0080800000FF;">then)</span>
<span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"HP%d%s = "</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">iter</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">niter</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</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;">"%s%d %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">e</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">else</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;">niter</span> <span style="color: #008080;">do</span>
Line 409 ⟶ 390:
<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: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s%s %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #000000;">res</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;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #7060A8;">papply</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">20</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)&</span><span style="color: #000000;">65</span><span style="color: #0000FF;">,</span><span style="color: #000000;">test</span><span style="color: #0000FF;">)</span>
<!--</lang>-->
{{out}}
Line 477 ⟶ 458:
= HP7_7_2688237874641409(1)
= 3_31_8308475676071413
HP65(19) = HP5_13(18)
= HP3_3_3_19(17)
= HP11_13_233(16)
= HP11_101203(15)
= HP3_3_23_53629(14)
= HP3_3_1523_24247(13)
= HP3_3_3_7_47_3732109(12)
= HP11_18013_16843763(11)
= HP151_740406071813(10)
= HP3_13_13_54833_5458223(9)
= HP3_3_97_179_373_7523_71411(8)
= HP1571_1601_1350675311441(7)
= HP3_3_13_33391_143947_279384649(6)
= HP11_23_204069263_6417517893491(5)
= HP7_11_1756639_83039633268945697(4)
= HP29_29_5165653_13503983_12122544283(3)
= HP228345060379_1282934064985326977(2)
= HP3_3_3_2979253_3030445387_9367290955541(1)
= 1381_3211183211_75157763339900357651 [13.9s]
</pre>
 
Petelomax
7,796

edits

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