12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849 |
- #!/usr/bin/ruby
- # Daniel "Trizen" Șuteu
- # Date: 20 July 2020
- # https://github.com/trizen
- # Algorithm with sublinear time for computing:
- #
- # Sum_{k=2..n} lpf(k)
- #
- # where:
- # lpf(k) = the least prime factor of k
- # See also:
- # https://projecteuler.net/problem=521
- func partial_sums_of_lpf(n) {
- var t = 0
- var s = n.isqrt
- s.each_prime {|p|
- t += p*p.rough_count(idiv(n,p))
- }
- t + sum_primes(s.next_prime, n)
- }
- for k in (1..7) {
- say "S(10^#{k}) = #{partial_sums_of_lpf(10**k)}"
- }
- __END__
- S(10^1) = 28
- S(10^2) = 1257
- S(10^3) = 79189
- S(10^4) = 5786451
- S(10^5) = 455298741
- S(10^6) = 37568404989
- S(10^7) = 3203714961609
- S(10^8) = 279218813374515
- S(10^9) = 24739731010688477
- S(10^10) = 2220827932427240957
- S(10^11) = 201467219561892846337
- S(10^12) = 18435592284459044389811
- S(10^13) = 1699246543196666002725979
- S(10^14) = 157589263416765879793706013
- S(10^15) = 14692398591103449239490624723
|