Primes - allocate descendants to their ancestors: Difference between revisions
Primes - allocate descendants to their ancestors (view source)
Revision as of 01:58, 6 October 2018
, 5 years ago→{{header|Phix}}
(Added Go) |
|||
Line 1,086:
99, 1 Ancestors: [17], 38257 Descendants: [194 1869 2225 2670 2848 ... 3904305912313344 4117822641892980 4392344151352512 4941387170271576 5559060566555523]
Total descendants: 546986</pre>
=={{header|Phix}}==
{{trans|Go}}
<lang Phix>constant maxSum = 99
function getPrimes()
sequence primes = {2}
for x=3 to maxSum by 2 do
bool zero = false
for i=1 to length(primes) do
if mod(x,primes[i]) == 0 then
zero = true
exit
end if
end for
if not zero then
primes = append(primes, x)
end if
end for
return primes
end function
function stringify(sequence s)
for i=1 to length(s) do
s[i] = sprintf("%d",s[i])
end for
return s
end function
procedure main()
atom t0 = time()
integer p
sequence descendants = repeat({},maxSum+1),
ancestors = repeat({},maxSum+1),
primes = getPrimes()
for i=1 to length(primes) do
p = primes[i]
descendants[p] = append(descendants[p], p)
for s=1 to length(descendants)-p do
descendants[s+p] &= sq_mul(descendants[s], p)
end for
end for
p = 4
for i=0 to length(primes) do
if i>0 then p = primes[i] end if
if length(descendants[p])!=0 then
descendants[p] = descendants[p][1..$-1]
end if
end for
integer total = 0
for s=1 to maxSum do
sequence x = sort(descendants[s])
total += length(x)
for i=1 to length(x) do
atom d = x[i]
if d>maxSum then exit end if
ancestors[d] &= append(ancestors[s], s)
end for
if s<26 or find(s,{46,74,99}) then
sequence d = ancestors[s]
integer l = length(d)
string sp = iff(l=1?" ":"s")
d = stringify(d)
printf(1,"%2d: %d Ancestor%s: [%-14s", {s, l, sp, join(d)&"]"})
d = sort(descendants[s])
l = length(d)
sp = iff(l=1?" ":"s")
if l<10 then
d = stringify(d)
else
d[4..-4] = {0}
d = stringify(d)
d[4] = "..."
end if
printf(1,"%5d Descendant%s: [%s]\n", {l, sp, join(d)})
end if
end for
printf(1,"\nTotal descendants %d\n", total)
?elapsed(time()-t0) -- < 1s
?elapsed(5559060566555523/4_000_000_000) -- > 16 days
end procedure
main()</lang>
{{out}}
<pre>
1: 0 Ancestors: [] 0 Descendants: []
2: 0 Ancestors: [] 0 Descendants: []
3: 0 Ancestors: [] 0 Descendants: []
4: 0 Ancestors: [] 0 Descendants: []
5: 0 Ancestors: [] 1 Descendant : [6]
6: 1 Ancestor : [5] 2 Descendants: [8 9]
7: 0 Ancestors: [] 2 Descendants: [10 12]
8: 2 Ancestors: [5 6] 3 Descendants: [15 16 18]
9: 2 Ancestors: [5 6] 4 Descendants: [14 20 24 27]
10: 1 Ancestor : [7] 5 Descendants: [21 25 30 32 36]
11: 0 Ancestors: [] 5 Descendants: [28 40 45 48 54]
12: 1 Ancestor : [7] 7 Descendants: [35 42 50 60 64 72 81]
13: 0 Ancestors: [] 8 Descendants: [22 56 63 75 80 90 96 108]
14: 3 Ancestors: [5 6 9] 10 Descendants: [33 49 70 ... 135 144 162]
15: 3 Ancestors: [5 6 8] 12 Descendants: [26 44 105 ... 192 216 243]
16: 3 Ancestors: [5 6 8] 14 Descendants: [39 55 66 ... 270 288 324]
17: 0 Ancestors: [] 16 Descendants: [52 88 99 ... 405 432 486]
18: 3 Ancestors: [5 6 8] 19 Descendants: [65 77 78 ... 576 648 729]
19: 0 Ancestors: [] 22 Descendants: [34 104 117 ... 810 864 972]
20: 3 Ancestors: [5 6 9] 26 Descendants: [51 91 130 ... 1215 1296 1458]
21: 2 Ancestors: [7 10] 30 Descendants: [38 68 195 ... 1728 1944 2187]
22: 1 Ancestor : [13] 35 Descendants: [57 85 102 ... 2430 2592 2916]
23: 0 Ancestors: [] 39 Descendants: [76 136 153 ... 3645 3888 4374]
24: 3 Ancestors: [5 6 9] 46 Descendants: [95 114 119 ... 5184 5832 6561]
25: 2 Ancestors: [7 10] 52 Descendants: [46 152 171 ... 7290 7776 8748]
46: 3 Ancestors: [7 10 25] 557 Descendants: [129 205 246 ... 15943230 17006112 19131876]
74: 5 Ancestors: [5 6 8 16 39] 6336 Descendants: [213 469 670 ... 470715894135 502096953744 564859072962]
99: 1 Ancestor : [17] 38257 Descendants: [194 1869 2225 ... 4392344151352512 4941387170271576 5559060566555523]
Total descendants 546986
"0.7s"
"16 days, 2 hours, 2 minutes and 45s"
</pre>
The quick test at the end suggests that a 4Ghz chip would take at least 16 days just to count to 5559060566555523, let alone
decompose those numbers into prime factors (and throwing away the ones you don't need, probably more like 10 million years),
which as requested in the task description obviously demonstrates that the algorithm can be crucial in terms of performance.
=={{header|Python}}==
| |||