1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556 |
- #!/usr/bin/ruby
- # Daniel "Trizen" Șuteu
- # Date: 07 June 2019
- # https://github.com/trizen
- # https://projecteuler.net/problem=668
- # Runtime: 1.535s (previously: 2.402s)
- # Formula:
- # R(n) = Sum_{sqrt(n) < p <= n} floor(n/p)
- #
- # a(n) = n - R(n) - Sum_{p <= sqrt(n)} (p-1) - pi(sqrt(n))
- # = n - R(n) - Sum_{p <= sqrt(n)} p
- #
- # where p runs over the prime numbers.
- # The interesting part is computing R(n) efficiently.
- # See also:
- # https://oeis.org/A064775 -- Card{ k<=n, k such that all prime divisors of k are <= sqrt(k) }.
- func R(n) {
- var p = next_prime(n.isqrt)
- var t = idiv(n,p)
- var sum = 0
- while (p <= n) {
- var u = idiv(n,p)
- if (u == t) {
- var q = next_prime(idiv(n,u))
- sum += u*prime_count(p, q-1)
- u = idiv(n,q)
- p = q
- }
- sum += u
- t = u
- p = p.next_prime
- }
- sum
- }
- func square_root_smooth_count (n) {
- n - n.isqrt.primes_sum - R(n)
- }
- say square_root_smooth_count(10_000_000_000)
|