Queries to count the number of unordered co | C ++ 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 ; Driver code ; function call
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define N  100005 NEW_LINE int phi [ N ] ; int S [ N ] ; void computeTotient ( ) { for ( int i = 1 ; i < N ; i ++ ) phi [ i ] = i ; for ( int p = 2 ; p < N ; p ++ ) { if ( phi [ p ] == p ) { phi [ p ] = p - 1 ; for ( int i = 2 * p ; i < N ; i += p ) { phi [ i ] = ( phi [ i ] / p ) * ( p - 1 ) ; } } } } void CoPrimes ( ) { computeTotient ( ) ; for ( int i = 1 ; i < N ; i ++ ) S [ i ] = S [ i - 1 ] + phi [ i ] ; } int main ( ) { CoPrimes ( ) ; int q [ ] = { 3 , 4 } ; int n = sizeof ( q ) / sizeof ( q [ 0 ] ) ; for ( int i = 0 ; i < n ; i ++ ) cout << " Number ▁ of ▁ unordered ▁ coprime STRNEWLINE " << " pairs ▁ of ▁ integers ▁ from ▁ 1 ▁ to ▁ " << q [ i ] << " ▁ are ▁ " << S [ q [ i ] ] << endl ; return 0 ; }