Rosetta Code

Strange unique prime triplets: Difference between revisions

Page Discussion

Strange unique prime triplets (view source)

Revision as of 10:54, 29 March 2021

12,463 bytes added ,  3 years ago
m
→‎{{header|Phix}}: added syntax colouring the hard way
(add FreeBASIC)
m (→‎{{header|Phix}}: added syntax colouring the hard way)
Line 1,391:
 
=={{header|Phix}}==
<!--<lang Phix>requires("0.8.4")-->
<span style="color: #7060A8;">requires</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"0.8.4"</span><span style="color: #0000FF;">)</span>
function create_sieve(integer limit)
<span style="color: #008080;">function</span> <span style="color: #000000;">create_sieve</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">limit</span><span style="color: #0000FF;">)</span>
sequence sieve = repeat(true,limit)
<span style="color: #004080;">sequence</span> <span style="color: #000000;">sieve</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #004600;">true</span><span style="color: #0000FF;">,</span><span style="color: #000000;">limit</span><span style="color: #0000FF;">)</span>
sieve[1] = false
<span style="color: #000000;">sieve</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: #004600;">false</span>
for i=4 to limit by 2 do
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">4</span> <span style="color: #008080;">to</span> <span style="color: #000000;">limit</span> <span style="color: #008080;">by</span> <span style="color: #000000;">2</span> <span style="color: #008080;">do</span>
sieve[i] = false
<span style="color: #000000;">sieve</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: #004600;">false</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
for p=3 to floor(sqrt(limit)) by 2 do
<span style="color: #008080;">for</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">=</span><span style="color: #000000;">3</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">sqrt</span><span style="color: #0000FF;">(</span><span style="color: #000000;">limit</span><span style="color: #0000FF;">))</span> <span style="color: #008080;">by</span> <span style="color: #000000;">2</span> <span style="color: #008080;">do</span>
integer p2 = p*p
<span style="color: #004080;">integer</span> <span style="color: #000000;">p2</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">*</span><span style="color: #000000;">p</span>
if sieve[p2] then
<span style="color: #008080;">if</span> <span style="color: #000000;">sieve</span><span style="color: #0000FF;">[</span><span style="color: #000000;">p2</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
for k=p2 to limit by p*2 do
<span style="color: #008080;">for</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">=</span><span style="color: #000000;">p2</span> <span style="color: #008080;">to</span> <span style="color: #000000;">limit</span> <span style="color: #008080;">by</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">*</span><span style="color: #000000;">2</span> <span style="color: #008080;">do</span>
sieve[k] = false
<span style="color: #000000;">sieve</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">for</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 sieve
<span style="color: #008080;">return</span> <span style="color: #000000;">sieve</span>
end function
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
procedure strange_triplets(integer lim, bool bCountOnly=true)
<span style="color: #008080;">procedure</span> <span style="color: #000000;">strange_triplets</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">lim</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">bool</span> <span style="color: #000000;">bCountOnly</span><span style="color: #0000FF;">=</span><span style="color: #004600;">true</span><span style="color: #0000FF;">)</span>
atom t0 = time(), t1 = t0+1
<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: #000000;">t1</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">t0</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span>
sequence primes = get_primes_le(lim),
<span style="color: #004080;">sequence</span> <span style="color: #000000;">primes</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">get_primes_le</span><span style="color: #0000FF;">(</span><span style="color: #000000;">lim</span><span style="color: #0000FF;">),</span>
sieve = create_sieve(lim*3),
<span style="color: #000000;">sieve</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">create_sieve</span><span style="color: #0000FF;">(</span><span style="color: #000000;">lim</span><span style="color: #0000FF;">*</span><span style="color: #000000;">3</span><span style="color: #0000FF;">),</span>
res = {}
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
atom count = 0
<span style="color: #004080;">atom</span> <span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
--
<span style="color: #000080;font-style:italic;">--
-- It is not worth involving 2, ie primes[1],
-- sinceIt (2is +not anyworth otherinvolving two2, primes)ie is evenprimes[1],
-- alsosince we(2 may+ asany wellother leavetwo spaceprimes) foris {j,k}even,
-- {k}also inwe themay twoas outerwell loops.leave space for {j,k},
-- Using{k} a sieve onin the inner testtwo isouter overloops.
-- Using a sieve on the inner test is over
-- ten times faster than is_prime(), whereas
-- ten times faster than is_prime(), whereas
-- using a separate table of primes for the
-- two outer loopsusing isa aboutseparate twicetable asof fastprimes asfor the
-- two outer loops is about twice as fast as
-- scanning the sieve skipping falsies. Also
-- scanning the sieve skipping falsies. Also
-- interestingly, using nm = n+m is twice as
-- fastinterestingly, asusing nmpnm = n+m+p. is twice as
-- fast as nmp = n+m+p.
--</span>
for i=2 to length(primes)-2 do
<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: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">primes</span><span style="color: #0000FF;">)-</span><span style="color: #000000;">2</span> <span style="color: #008080;">do</span>
integer n = primes[i]
<span style="color: #004080;">integer</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">primes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
for j=i+1 to length(primes)-1 do
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</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;">primes</span><span style="color: #0000FF;">)-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
integer m = primes[j],
<span style="color: #004080;">integer</span> <span style="color: #000000;">m</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">primes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">],</span>
nm = n+m
<span style="color: #000000;">nm</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">m</span>
for k=j+1 to length(primes) do
<span style="color: #008080;">for</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">=</span><span style="color: #000000;">j</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;">primes</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
integer p = primes[k],
<span style="color: #004080;">integer</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">primes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">],</span>
nmp = nm+p
<span style="color: #000000;">nmp</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">nm</span><span style="color: #0000FF;">+</span><span style="color: #000000;">p</span>
if sieve[nmp] then
<span style="color: #008080;">if</span> <span style="color: #000000;">sieve</span><span style="color: #0000FF;">[</span><span style="color: #000000;">nmp</span><span style="color: #0000FF;">]</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 not bCountOnly then
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #000000;">bCountOnly</span> <span style="color: #008080;">then</span>
res = append(res,sprintf("%2d: %2d+%2d+%2d = %d",
<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: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"%2d: %2d+%2d+%2d = %d"</span><span style="color: #0000FF;">,</span>
{count, n, m, p, nmp}))
<span style="color: #0000FF;">{</span><span style="color: #000000;">count</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">nmp</span><span style="color: #0000FF;">}))</span>
end if
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
if time()>t1 then
<span style="color: #008080;">if</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()></span><span style="color: #000000;">t1</span> <span style="color: #008080;">then</span>
progress("Working... (%,d)\r",{count})
<span style="color: #7060A8;">progress</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"Working... (%,d)\r"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">count</span><span style="color: #0000FF;">})</span>
t1 = time()+1
<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>
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>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
progress("")
<span style="color: #7060A8;">progress</span><span style="color: #0000FF;">(</span><span style="color: #008000;">""</span><span style="color: #0000FF;">)</span>
string r = iff(bCountOnly?sprintf(" (%s)",{elapsed(time()-t0)})
<span style="color: #004080;">string</span> <span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">bCountOnly</span><span style="color: #0000FF;">?</span><span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">" (%s)"</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>
:sprintf(":\n%s",{join(shorten(res,"",3),"\n")}))
<span style="color: #0000FF;">:</span><span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">":\n%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;">res</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;">"\n"</span><span style="color: #0000FF;">)}))</span>
printf(1,"%,d strange triplets < %,d found%s\n\n",{count,lim,r})
<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 strange triplets &lt; %,d found%s\n\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">count</span><span style="color: #0000FF;">,</span><span style="color: #000000;">lim</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r</span><span style="color: #0000FF;">})</span>
end procedure
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
strange_triplets(30,false)
<span style="color: #000000;">strange_triplets</span><span style="color: #0000FF;">(</span><span style="color: #000000;">30</span><span style="color: #0000FF;">,</span><span style="color: #004600;">false</span><span style="color: #0000FF;">)</span>
strange_triplets(1000)
<span style="color: #000000;">strange_triplets</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1000</span><span style="color: #0000FF;">)</span>
strange_triplets(10000)</lang>
<span style="color: #000000;">strange_triplets</span><span style="color: #0000FF;">(</span><span style="color: #000000;">10000</span><span style="color: #0000FF;">)</span>
<!--</lang>-->
{{out}}
<pre>
Petelomax
7,820

edits

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