Rosetta Code

Long primes: Difference between revisions

Page Discussion

Long primes (view source)

Revision as of 14:57, 25 May 2021

12,422 bytes added ,  2 years ago
m
→‎{{header|Phix}}: added syntax colouring the hard way
(Added AppleScript.)
m (→‎{{header|Phix}}: added syntax colouring the hard way)
Line 2,169:
=={{header|Phix}}==
Slow version:
<!--<lang Phix>function is_long_prime(integer nphixonline)-->
<span style="color: #008080;">function</span> <span style="color: #000000;">is_long_prime</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
integer r = 1, rr, period = 0
<span style="color: #004080;">integer</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;">rr</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">period</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
for i=1 to n+1 do
<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: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
r = mod(10*r,n)
<span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">10</span><span style="color: #0000FF;">*</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
rr = r
<span style="color: #000000;">rr</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">r</span>
while true do
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
r = mod(10*r,n)
<span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">10</span><span style="color: #0000FF;">*</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
period += 1
<span style="color: #000000;">period</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
if period>=n then return false end if
<span style="color: #008080;">if</span> <span style="color: #000000;">period</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: #004600;">false</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
if r=rr then exit end if
<span style="color: #008080;">if</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">=</span><span style="color: #000000;">rr</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>
end while
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
return period=n-1
<span style="color: #008080;">return</span> <span style="color: #000000;">period</span><span style="color: #0000FF;">=</span><span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span>
end function</lang>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<!--</lang>-->
(use the same main() as below but limit maxN to 8 iterations)
 
Much faster version:
<!--<lang Phix>function is_long_prime(integer nphixonline)-->
<span style="color: #008080;">function</span> <span style="color: #000000;">is_long_prime</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
sequence f = factors(n-1,1)
<span style="color: #004080;">sequence</span> <span style="color: #000000;">f</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">factors</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</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>
integer count = 0
<span style="color: #004080;">integer</span> <span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
for i=1 to length(f) do
<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;">f</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
integer fi = f[i], e=1, base=10
<span style="color: #004080;">integer</span> <span style="color: #000000;">fi</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">f</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">e</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">base</span><span style="color: #0000FF;">=</span><span style="color: #000000;">10</span>
while fi!=0 do
<span style="color: #008080;">while</span> <span style="color: #000000;">fi</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">do</span>
if mod(fi,2)=1 then
<span style="color: #008080;">if</span> <span style="color: #7060A8;">mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">fi</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>
e = mod(e*base,n)
<span style="color: #000000;">e</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">e</span><span style="color: #0000FF;">*</span><span style="color: #000000;">base</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
end if
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
base = mod(base*base,n)
<span style="color: #000000;">base</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">base</span><span style="color: #0000FF;">*</span><span style="color: #000000;">base</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
fi = floor(fi/2)
<span style="color: #000000;">fi</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">fi</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
end while
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
if e=1 then
<span style="color: #008080;">if</span> <span style="color: #000000;">e</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
count += 1
<span style="color: #000000;">count</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
if count>1 then exit end if
<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;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
end if
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
return count=1
<span style="color: #008080;">return</span> <span style="color: #000000;">count</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span>
end function
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
 
procedure main()
<span style="color: #008080;">procedure</span> <span style="color: #000000;">main</span><span style="color: #0000FF;">()</span>
atom t0 = time()
<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>
integer maxN = 500*power(2,14)
<span style="color: #004080;">integer</span> <span style="color: #000000;">maxN</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">500</span><span style="color: #0000FF;">*</span><span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">14</span><span style="color: #0000FF;">)</span>
--integer maxN = 500*power(2,7) -- (slow version)
<span style="color: #000080;font-style:italic;">--integer maxN = 500*power(2,7) -- (slow version)</span>
sequence long_primes = {}
<span style="color: #004080;">sequence</span> <span style="color: #000000;">long_primes</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
integer count = 0,
<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>
n = 500,
<span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">500</span><span style="color: #0000FF;">,</span>
i = 2
<span style="color: #000000;">i</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">2</span>
while true do
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
integer prime = get_prime(i)
<span style="color: #004080;">integer</span> <span style="color: #000000;">prime</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">get_prime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">)</span>
if is_long_prime(prime) then
<span style="color: #008080;">if</span> <span style="color: #000000;">is_long_prime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">prime</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
if prime<500 then
<span style="color: #008080;">if</span> <span style="color: #000000;">prime</span><span style="color: #0000FF;"><</span><span style="color: #000000;">500</span> <span style="color: #008080;">then</span>
long_primes &= prime
<span style="color: #000000;">long_primes</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">prime</span>
end if
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
if prime>n then
<span style="color: #008080;">if</span> <span style="color: #000000;">prime</span><span style="color: #0000FF;">></span><span style="color: #000000;">n</span> <span style="color: #008080;">then</span>
if n=500 then
<span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">500</span> <span style="color: #008080;">then</span>
printf(1,"The long primes up to 500 are:\n %v\n",{long_primes})
<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;">"The long primes up to 500 are:\n %V\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">long_primes</span><span style="color: #0000FF;">})</span>
printf(1,"\nThe number of long primes up to:\n")
<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;">"\nThe number of long primes up to:\n"</span><span style="color: #0000FF;">)</span>
end if
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
printf(1," %7d is %d (%s)\n", {n, count, elapsed(time()-t0)})
<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;">" %7d is %d (%s)\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;">count</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>
if n=maxN then exit end if
<span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">maxN</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>
n *= 2
<span style="color: #000000;">n</span> <span style="color: #0000FF;">*=</span> <span style="color: #000000;">2</span>
end if
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
count += 1
<span style="color: #000000;">count</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
end if
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
i += 1
<span style="color: #000000;">i</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
end while
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
end procedure
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
main()</lang>
<span style="color: #000000;">main</span><span style="color: #0000FF;">()</span>
<!--</lang>-->
{{out}}
slow version:
Petelomax
7,795

edits

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