#1**0 **

i=0;a=1;b=1000000;c=60;cycle:d=a;if(gcd(c,d)==1,goto end, goto next);end:print d,", ",;i++; next: a=a+1;if(a<=b, goto cycle, 0);print"Total No. of coprimes ==", i

**OUTPUT==266,666 integers between 1 and 1,000,000 that are relatively prime to 60**

Guest Apr 16, 2022

#2**+1 **

For an integer to be relatively prime to 60, it has to be:

(i) not divisible by 2

(ii) not divisible by 3

(iii) not divisible by 5

By inclusion-exclusion principle and using the fact that \(\text{# of integers in }[1, N]\text{ divisible by }k = \left\lfloor\dfrac{N}k\right\rfloor\),

\(\begin{array}{cl} &\text{# of numbers relatively prime to 60}\\ =& 1000000 - \left\lfloor\dfrac{1000000}2\right\rfloor - \left\lfloor\dfrac{1000000}3\right\rfloor - \left\lfloor\dfrac{1000000}5\right\rfloor + \left\lfloor\dfrac{1000000}6\right\rfloor + \left\lfloor\dfrac{1000000}{10}\right\rfloor + \left\lfloor\dfrac{1000000}{15}\right\rfloor-\left\lfloor\dfrac{1000000}{30}\right\rfloor \\=&266666\end{array}\)

MaxWong Apr 16, 2022