Rosetta Code

Least m such that n! + m is prime: Difference between revisions

Page Discussion

Least m such that n! + m is prime (view source)

Revision as of 18:30, 17 December 2023

5,356 bytes removed ,  6 months ago
m
→‎{{header|Phix}}: use pygments, added progress and full run times
(Added Algol 68)
m (→‎{{header|Phix}}: use pygments, added progress and full run times)
Line 278:
=={{header|Phix}}==
{{trans|C}}
<!--<syntaxhighlight lang="phix">(phixonline)-->
atom t0 = time()
<span style="color: #7060A8;">requires</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"1.0.3"</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- mpz_nextprime() added </span>
requires("1.0.3") -- mpz_nextprime() added
<span style="color: #008080;">constant</span> <span style="color: #000000;">LIMIT</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">10000</span>
constant LIMIT = 10000
<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span>
include mpfr.e
<span style="color: #004080;">mpz</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">fact</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_inits</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: #0000FF;">)</span>
mpz {fact, p} = mpz_inits(2,1)
<span style="color: #004080;">sequence</span> <span style="color: #000000;">diffs</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
sequence diffs = {}
<span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1000</span>
integer n=0, m, t = 1000
<span style="color: #008080;">while</span> <span style="color: #000000;">t</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">LIMIT</span> <span style="color: #008080;">do</span>
while t<=LIMIT do
<span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">></span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #7060A8;">mpz_mul_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">fact</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">fact</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;">if</span>
progress("position: %d\r",{n})
<span style="color: #000000;">mpz_nextprime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">fact</span><span style="color: #0000FF;">)</span>
if n>0 then mpz_mul_si(fact, fact, n) end if
<span style="color: #7060A8;">mpz_sub</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">fact</span><span style="color: #0000FF;">);</span>
mpz_nextprime(p, fact)
<span style="color: #000000;">m</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_get_integer</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">);</span>
mpz_sub(p, p, fact);
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">diffs</span><span style="color: #0000FF;">)<</span><span style="color: #000000;">50</span> <span style="color: #008080;">then</span>
m = mpz_get_integer(p);
<span style="color: #000000;">diffs</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">m</span>
if length(diffs)<50 then
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">diffs</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">50</span> <span style="color: #008080;">then</span>
diffs &= m
<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;">"Least positive m such that n! + m is prime; first 50:\n%s\n"</span><span style="color: #0000FF;">,</span>
if length(diffs)=50 then
<span style="color: #0000FF;">{</span><span style="color: #7060A8;">join_by</span><span style="color: #0000FF;">(</span><span style="color: #000000;">diffs</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</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;">"%3d"</span><span style="color: #0000FF;">)})</span>
printf(1,"Least positive m such that n! + m is prime; first 50:\n%s\n",
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
{join_by(diffs,1,10," ", fmt:="%3d")})
<span style="color: #008080;">elsif</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">></span><span style="color: #000000;">t</span> <span style="color: #008080;">then</span>
end if
<span style="color: #008080;">do</span>
elsif m>t then
<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;">"First m &gt; %,6d is %,6d at position %,d\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">})</span>
string e = elapsed(time()-t0,0," (%s)")
<span style="color: #000000;">t</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1000</span>
do
<span style="color: #008080;">until</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">></span><span style="color: #000000;">m</span>
printf(1,"First m > %,6d is %,6d at position %,d%s\n", {t, m, n, e})
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
e = ""
<span style="color: #000000;">n</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
t += 1000
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
until t>m
<!--</syntaxhighlight>-->▼
end if
n += 1
end while
?elapsed(time()-t0)
▲<!--</syntaxhighlight>-->
{{out}}
<pre>
Line 314 ⟶ 319:
53 1 97 71 47 239 101 233 53 83
 
First m > 1,000 is 1,069 at position 107 (0.2s)
First m > 2,000 is 3,391 at position 192 (3.4s)
First m > 3,000 is 3,391 at position 192
First m > 4,000 is 4,943 at position 284 (27.3s)
First m > 5,000 is 5,233 at position 384 (2 minutes and 15s)
First m > 6,000 is 6,131 at position 388
First m > 7,000 is 9,067 at position 445 (4 minutes and 56s)
First m > 8,000 is 9,067 at position 445
First m > 9,000 is 9,067 at position 445
First m > 10,000 is 12,619 at position 599 (26 minutes and 15s)
First m > 11,000 is 12,619 at position 599
First m > 12,000 is 12,619 at position 599
"26 minutes and 15s"
</pre>
For comparison, the Julia entry above took 18 mins 38s on the same box.
Note this is very slow, and ''still'' running..... so I killed it there
 
=={{header|Quackery}}==
Petelomax
7,820

edits

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