问题
考虑分数\(\frac{n}{d}\)，n和d都是正整数。如果n<d、且n与d互质（HCF(n,d)=GCD(n,d)=1），那么这个分数则被称为简分数。
如果我们将d≤8的简分数从值的小到大排列，会得到：
\(\frac{1}{8}, \frac{1}{7}, \frac{1}{6}, \frac{1}{5}, \frac{1}{4}, \frac{2}{7}, \frac{1}{3}, \frac{3}{8}, \frac{2}{5}, \frac{3}{7}, \frac{1}{2}, \frac{4}{7}, \frac{3}{5}, \frac{5}{8}, \frac{2}{3}, \frac{5}{7}, \frac{3}{4}, \frac{4}{5}, \frac{5}{6}, \frac{6}{7}, \frac{7}{8}\)
可以看出，这个集合有21个元素。
那么请问，当d ≤ 1,000,000，集合里面有多少个简分数？
* 传送门
分析
考究永远不怕太深。这个问题在《问题71》已经探讨过：\(|F_n| = \sum_{i=2}^n \phi(i)\)。
答案
// answer: using formula
const start = Date.now()
function* primes_below(n) {
const m = Math.floor((n - 2) / 2)
const sieve = new BitSet
for (let i = 1; i < m; ++i) {
let j = i, p = i + j + 2*i*j
for (; p <= m; ++j, p = i + j + 2*i*j)
sieve.set(p, 1)
}
yield 2
for (let i = 1; i <= m; ++i)
if (sieve.get(i) == 0)
yield (2*i + 1)
}
const limit = 1000000
const is_prime = new BitSet
for (const prime of primes_below(limit))
is_prime.set(prime, 1)
function prime_factors(n) {
const primes = []
function divide_test(p) {
if (is_prime.get(p)) {
let divisible = false
while ((n % p) == 0) {
n /= p
divisible = true
}
if (divisible)
primes.push(p)
}
}
let i = 2
divide_test(i++)
for (; n > 2 && !is_prime.get(n); i += 2)
divide_test(i)
if (n > 1)
primes.push(n)
return primes
}
function phi(n) {
if (n == 1)
return 1
if (is_prime.get(n))
return n-1
let numerator = 1, denominator = 1
for (const p of prime_factors(n)) {
numerator *= p - 1
denominator *= p
}
return n*numerator/denominator
}
let result = 0
for (let n = 2; n <= limit; ++n)
result += phi(n)
alert(result + ', ' + (Date.now()-start) + 'ms')
