Proper divisors: Difference between revisions
Content added Content deleted
m (→{{header|Phix}}: added syntax colouring the hard way) |
|||
| Line 3,855: | Line 3,855: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
The factors routine is an auto-include. The actual implementation of it, from builtins\pfactors.e is |
The factors routine is an auto-include. The actual implementation of it, from builtins\pfactors.e is |
||
<!--<lang Phix>--> |
|||
<lang Phix>global function factors(atom n, integer include1=0) |
|||
<span style="color: #008080;">global</span> <span style="color: #008080;">function</span> <span style="color: #7060A8;">factors</span><span style="color: #0000FF;">(</span><span style="color: #004080;">atom</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">include1</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span> |
|||
-- |
|||
<span style="color: #000080;font-style:italic;">-- |
|||
-- returns a list of all integer factors of n |
-- returns a list of all integer factors of n |
||
| ⚫ | |||
-- if include1 is |
-- if include1 is 0 (the default), result does not contain either 1 or n |
||
-- if include1 is |
-- if include1 is 1 the result contains 1 and n |
||
| ⚫ | |||
-- |
|||
-- </span> |
|||
if n=0 then return {} end if |
|||
<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: #008080;">return</span> <span style="color: #0000FF;">{}</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
sequence lfactors = {}, hfactors = {} |
|||
<span style="color: #000000;">check_limits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"factors"</span><span style="color: #0000FF;">)</span> |
|||
atom hfactor |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">lfactors</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{},</span> <span style="color: #000000;">hfactors</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span> |
|||
integer p = 2, |
|||
<span style="color: #004080;">atom</span> <span style="color: #000000;">hfactor</span> |
|||
lim = floor(sqrt(n)) |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> |
|||
<span style="color: #000000;">lim</span> <span style="color: #0000FF;">=</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;">n</span><span style="color: #0000FF;">))</span> |
|||
if include1!=0 then |
|||
lfactors = {1} |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">include1</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> |
|||
if n!=1 and include1=1 then |
|||
<span style="color: #000000;">lfactors</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}</span> |
|||
hfactors = {n} |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">1</span> <span style="color: #008080;">and</span> <span style="color: #000000;">include1</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> |
|||
end if |
|||
<span style="color: #000000;">hfactors</span> <span style="color: #0000FF;">=</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> |
|||
while p<=lim do |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
if remainder(n,p)=0 then |
|||
<span style="color: #008080;">while</span> <span style="color: #000000;">p</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">lim</span> <span style="color: #008080;">do</span> |
|||
lfactors = append(lfactors,p) |
|||
<span style="color: #008080;">if</span> <span style="color: #7060A8;">remainder</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> |
|||
hfactor = n/p |
|||
<span style="color: #000000;">lfactors</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">lfactors</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)</span> |
|||
if hfactor=p then exit end if |
|||
<span style="color: #000000;">hfactor</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">/</span><span style="color: #000000;">p</span> |
|||
hfactors = prepend(hfactors,hfactor) |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">hfactor</span><span style="color: #0000FF;">=</span><span style="color: #000000;">p</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: #000000;">hfactors</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">prepend</span><span style="color: #0000FF;">(</span><span style="color: #000000;">hfactors</span><span style="color: #0000FF;">,</span><span style="color: #000000;">hfactor</span><span style="color: #0000FF;">)</span> |
|||
p += 1 |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
end while |
|||
<span style="color: #000000;">p</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
|||
return lfactors & hfactors |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
|||
end function</lang> |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">lfactors</span> <span style="color: #0000FF;">&</span> <span style="color: #000000;">hfactors</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
<!--</lang>--> |
|||
The compiler knows where to find that, so the main program is just: |
The compiler knows where to find that, so the main program is just: |
||
<lang Phix> |
<!--<lang Phix>(phixonline)--> |
||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">10</span> <span style="color: #008080;">do</span> |
|||
printf(1,"%d: %v\n",{i,factors(i,-1)}) |
|||
<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: %v\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">factors</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: #0000FF;">)})</span> |
|||
end for |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
sequence candidates = {} |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">candidates</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span> |
|||
integer maxd = 0 |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">maxd</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> |
|||
for i=1 to 20000 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;">20000</span> <span style="color: #008080;">do</span> |
|||
integer k = length(factors(i,-1)) |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">factors</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: #0000FF;">))</span> |
|||
if k>=maxd then |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">maxd</span> <span style="color: #008080;">then</span> |
|||
if k=maxd then |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">=</span><span style="color: #000000;">maxd</span> <span style="color: #008080;">then</span> |
|||
candidates &= i |
|||
<span style="color: #000000;">candidates</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">i</span> |
|||
else |
|||
<span style="color: #008080;">else</span> |
|||
<span style="color: #000000;">candidates</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">i</span><span style="color: #0000FF;">}</span> |
|||
maxd = k |
|||
<span style="color: #000000;">maxd</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">k</span> |
|||
end if |
|||
<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> |
|||
printf(1,"%d divisors: %v\n", {maxd,candidates})</lang> |
|||
<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 divisors: %v\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">maxd</span><span style="color: #0000FF;">,</span><span style="color: #000000;">candidates</span><span style="color: #0000FF;">})</span> |
|||
<!--</lang>--> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||