1234567891011121314151617181920212223242526272829 |
- #!/usr/bin/ruby
- # Daniel "Trizen" Șuteu
- # Date: 22 May 2020
- # https://github.com/trizen
- # Twos are all you need
- # https://projecteuler.net/problem=708
- # Solution by counting the number of k-almost primes <= n.
- # Let:
- # pi_k(n) = the number of k-almost primes <= n.
- # Then:
- # S(n) = Sum_{k=1..n} 2^bigomega(k)
- # = Sum_{k=0..floor(log_2(n))} 2^k * pi_k(n)
- # Runtime: 0.371s (previously 5.876s)
- func S(n) {
- sum(0..n.ilog2, {|k|
- 2**k * k.almost_primepi(n)
- })
- }
- say ("S(10^8) = ", S(10**8))
- say ("S(10^14) = ", S(10**14))
|