Powerful numbers: Difference between revisions
m
→{{header|Wren}}: Minor tidy
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
m (→{{header|Wren}}: Minor tidy) |
||
| (2 intermediate revisions by 2 users not shown) | |||
Line 42:
<br><br>
=={{header|11l}}==
{{trans|Python}}
<syntaxhighlight lang="11l">
F primes_up_to_limit(Int limit)
[Int] r
I limit >= 2
r.append(2)
V isprime = [1B] * ((limit - 1) I/ 2)
V sieveend = Int(sqrt(limit))
L(i) 0 .< isprime.len
I isprime[i]
Int p = i * 2 + 3
r.append(p)
I i <= sieveend
L(j) ((p * p - 3) >> 1 .< isprime.len).step(p)
isprime[j] = 0B
R r
F primepowers(k, upper_bound)
V ub = Int(pow(upper_bound, 1 / k) + .5)
V res = [[Int64(1)]]
L(p) primes_up_to_limit(ub)
V a = [Int64(p) ^ k]
V u = upper_bound I/ a.last
L u >= p
a.append(a.last * p)
u I/= p
res.append(a)
R res
F kpowerful(k, upper_bound)
V ps = primepowers(k, upper_bound)
F accu(Int i, Int64 ub) -> [Int64]
[Int64] c
L(p) @ps[i]
V u = ub I/ p
I !u
L.break
c [+]= p
L(j) i + 1 .< @ps.len
I u < @ps[j][0]
L.break
c [+]= @accu(j, u).map(x -> @p * x)
R c
R sorted(accu(0, upper_bound))
F kpowerful_count_only(k, upper_bound)
V ps = primepowers(k, upper_bound)
F accu(Int i, Int64 ub) -> Int
V c = 0
L(p) @ps[i]
V u = ub I/ p
I !u
L.break
c++
L(j) i + 1 .< @ps.len
I u < @ps[j][0]
L.break
c += @accu(j, u)
R c
R accu(0, upper_bound)
L(k) 2..10
V res = kpowerful(k, Int64(10) ^ k)
print(res.len‘ ’k‘-powerfuls up to 10^’k‘: ’(
res[0.<5].map(x -> String(x)).join(‘ ’))‘ ... ’(
res[(len)-5..].map(x -> String(x)).join(‘ ’)))
L(k) 2..9
V res = (0 .< k + 10).map(n -> kpowerful_count_only(@k, Int64(10) ^ n))
print(k‘-powerful up to 10^’(k + 10)‘: ’res.map(x -> String(x)).join(‘ ’))
</syntaxhighlight>
{{out}}
<pre>
14 2-powerfuls up to 10^2: 1 4 8 9 16 ... 49 64 72 81 100
20 3-powerfuls up to 10^3: 1 8 16 27 32 ... 625 648 729 864 1000
25 4-powerfuls up to 10^4: 1 16 32 64 81 ... 5184 6561 7776 8192 10000
32 5-powerfuls up to 10^5: 1 32 64 128 243 ... 65536 69984 78125 93312 100000
38 6-powerfuls up to 10^6: 1 64 128 256 512 ... 559872 746496 823543 839808 1000000
46 7-powerfuls up to 10^7: 1 128 256 512 1024 ... 7558272 8388608 8957952 9765625 10000000
52 8-powerfuls up to 10^8: 1 256 512 1024 2048 ... 60466176 67108864 80621568 90699264 100000000
59 9-powerfuls up to 10^9: 1 512 1024 2048 4096 ... 644972544 725594112 816293376 967458816 1000000000
68 10-powerfuls up to 10^10: 1 1024 2048 4096 8192 ... 7739670528 8589934592 8707129344 9795520512 10000000000
2-powerful up to 10^12: 1 4 14 54 185 619 2027 6553 21044 67231 214122 680330
3-powerful up to 10^13: 1 2 7 20 51 129 307 713 1645 3721 8348 18589 41136
4-powerful up to 10^14: 1 1 5 11 25 57 117 235 464 906 1741 3312 6236 11654
5-powerful up to 10^15: 1 1 3 8 16 32 63 117 211 375 659 1153 2000 3402 5770
6-powerful up to 10^16: 1 1 2 6 12 21 38 70 121 206 335 551 900 1451 2326 3706
7-powerful up to 10^17: 1 1 1 4 10 16 26 46 77 129 204 318 495 761 1172 1799 2740
8-powerful up to 10^18: 1 1 1 3 8 13 19 32 52 85 135 211 315 467 689 1016 1496 2191
9-powerful up to 10^19: 1 1 1 2 6 11 16 24 38 59 94 145 217 317 453 644 919 1308 1868
</pre>
=={{header|C++}}==
Line 54 ⟶ 160:
bool is_square_free(uint64_t n) {
if (n % 4 == 0)
return false;
for (uint64_t p =
for (
}
return true;
Line 1,213 ⟶ 1,317:
{{libheader|Wren-sort}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="
import "./set" for Set
import "./sort" for Sort
import "./fmt" for Fmt
var potentialPowerful = Fn.new { |max, k|
| |||