+0  
 
0
37
2
avatar

How many integers between 1 and 1,000,000 are relatively prime to \(60\).

 Apr 16, 2022
 #1
avatar
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

 Apr 16, 2022
 #2
avatar+9363 
+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}\)

 Apr 16, 2022
edited by MaxWong  Apr 16, 2022

18 Online Users