Question

How many of the first million positive integers share no common factors greater than 1 with 2020

Answer 1

9514 1404 393

Answer:

  396,040

Step-by-step explanation:

Factors of 2020 are 2, 5, 101.

There are 1,000,000 / 1010 = 990 multiples of 2 and 5 and 101.

There are 1,000,000 / 505 -990 = 990 multiples of 5 and 101 only.

There are 1,000,000 / 202 -990 = 3,960 multiples of 2 and 101 only.

There are 1,000,000 / 10 - 990 = 99,010 multiples of 2 and 5 only.

There are 1,000,000 / 101 -990 -990 -3960 = 3,960 multiples of 101 only.

There are 1,000,000 / 5 -990 -990 -99,010 = 99,010 multiples of 5 only.

There are 1,000,000 / 2 -990 -3960 -99,010 = 396,040 multiples of 2 only.

So, the total number of multiples of any factor of 2020 is ...

  990 +990 +3960 +99,010 +3960 +99010 +396040 = 603960

Then the number of integers in the first million that do not share any common factors greater than 1 with 2020 is ...

  1,000,000 -603,960 = 396,040