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
+9519 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}\)
