/* Totatives In number theory, Euler's totient function (phi function) counts the positive integers up to a given integer n that are relatively prime to n. Two integers are said to be relatively prime if the only positive integer (factor) that divides both of them is 1. The numbers less than or equal to and relatively prime to a given number n are called totatives. For example: Input: 9 Output: 6 (The totatives of n = 9 are six numbers 1, 2, 4, 5, 7 and 8, so phi(9) = 6 because 3, 6 and 9 are not relatively prime with 9) Note that, phi(1)=1 because 1 is considered to be relatively prime to every positive number. Write a program to take positive integer n as an input and print the number of totatives in the numbers less than or equal to n. */ #include #include using namespace std; bool isRelativePrime( unsigned int a , unsigned int b ) { if ( 1 == a ) return true ; unsigned int rem = b % a; if ( 0 == rem ) return false; if ( 1 == rem ) return true; return isRelativePrime( rem , a ); } unsigned int phi( unsigned int num ) { unsigned int output = 0; for ( unsigned int i = 1 ; i <= num ; ++i ){ if ( isRelativePrime( i , num ) ){ output++; cout<< i << " "; } } cout<< " \ntot : "; return output ; } unsigned int phiBig( unsigned int num ) { vector jumps; vector::iterator jt; unsigned int output = 1; bool tojump; //unsigned int jump = 1; for ( unsigned int i = 2 ; i < num ; ++i ){ tojump = false ; for ( jt = jumps.begin() ; jt != jumps.end() ; ++jt ) if ( 0 == i % *jt ){ tojump = true; break ; } if ( tojump ) continue; if ( isRelativePrime( i , num ) ) output++; else jumps.push_back( i ); } cout<< " \ntot : "; return output ; } void check( unsigned int num ) { cout << " phi --> "<>x; cout << "Submitted value\n"; check( x ); cout << "\n * * * * * * * * * *\n"; cout << "Test cases..\n"; check(1); check(2); check(3); check(4); check(5); check(6); check(7); check(8); check(9); check(10); check(11); check(12); check(20); check(30); check(31); check(33); check(100); check(98); return 0; }

TOTATIVES [CHALLENGE]