Queries to count the number of unordered co | PHP program to find number of unordered coprime pairs of integers from 1 to N ; to store euler 's totient function ; to store required answer ; Computes and prints totient of all numbers smaller than or equal to N . ; Initialise the phi [ ] with 1 ; Compute other Phi values ; If phi [ p ] is not computed already , then number p is prime ; Phi of a prime number p is always equal to p - 1. ; Update phi values of all multiples of p ; Add contribution of p to its multiple i by multiplying with ( 1 - 1 / p ) ; function to compute number coprime pairs ; function call to compute euler totient function ; prefix sum of all euler totient function values ; function call
< ? php $ N = 100005 ; $ phi = array_fill ( 0 , $ N , 0 ) ; $ S = array_fill ( 0 , $ N , 0 ) ; function computeTotient ( ) { global $ N , $ phi , $ S ; for ( $ i = 1 ; $ i < $ N ; $ i ++ ) $ phi [ $ i ] = $ i ; for ( $ p = 2 ; $ p < $ N ; $ p ++ ) { if ( $ phi [ $ p ] == $ p ) { $ phi [ $ p ] = $ p - 1 ; for ( $ i = 2 * $ p ; $ i < $ N ; $ i += $ p ) { $ phi [ $ i ] = ( int ) ( ( $ phi [ $ i ] / $ p ) * ( $ p - 1 ) ) ; } } } } function CoPrimes ( ) { global $ N , $ phi , $ S ; computeTotient ( ) ; for ( $ i = 1 ; $ i < $ N ; $ i ++ ) $ S [ $ i ] = $ S [ $ i - 1 ] + $ phi [ $ i ] ; } CoPrimes ( ) ; $ q = array ( 3 , 4 ) ; $ n = sizeof ( $ q ) ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) echo " Number ▁ of ▁ unordered ▁ coprime STRNEWLINE " . " pairs ▁ of ▁ integers ▁ from ▁ 1 ▁ to ▁ " . $ q [ $ i ] . " ▁ are ▁ " . $ S [ $ q [ $ i ] ] . " STRNEWLINE " ; ? >