In this challenge, you will be writing a piece of code that generates the first N numbers in OEIS sequence A000010, the Euler totient function phi(n).
This sequence is defined as the "count of numbers <= n and prime to n." In other words, the value of the function for an input
n
is the count of numbers in {1, 2, 3, ..., n}
that are relatively prime to n
-- that is, the numbers whose GCD (Greatest
Common Divisor) with n
is 1
.
When run, your program should output the first 100 numbers in this sequence. This is equivalent to outputting the value of
[ phi(n) for n in range(1, 100) ]
These numbers are:
1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6,
8, 8, 16, 6, 18, 8, 12, 10, 22, 8, 20, 12,
18, 12, 28, 8, 30, 16, 20, 16, 24, 12, 36,
18, 24, 16, 40, 12, 42, 20, 24, 22, 46, 16,
42, 20, 32, 24, 52, 18, 40, 24, 36, 28, 58,
16, 60, 30, 36, 32, 48, 20, 66, 32, 44