Given a number N. The task is to find the number of unordered coprime pairs of integers from 1 to N. There can be multiple queries.
Examples:
Input: 3 Output: 4 (1, 1), (1, 2), (1, 3), (2, 3) Input: 4 Output: 6 (1, 1), (1, 2), (1, 3), (1, 4), (2, 3), (3, 4)
Approach: Here Euler’s Totient Function will be helpful. Euler’s totient function denoted as phi(N), is an arithmetic function that counts the positive integers less than or equal to N that are relatively prime to N.
The idea is to use the following properties of Euler Totient function i.e.
- The formula basically says that the value of ?(n) is equal to n multiplied by product of (1 – 1/p) for all prime factors p of n. For example value of ?(6) = 6 * (1-1/2) * (1 – 1/3) = 2.
- For a prime number p, ?(p) is p-1. For example ?(5) is 4, ?(7) is 6 and ?(13) is 12. This is obvious, gcd of all numbers from 1 to p-1 will be 1 because p is a prime.
Now, find the sum of all phi(x) for all i between 1 to N using prefix sum method. Using this, one can answer in o(1) time.
Below is the implementation of above approach.
C++
// C++ program to find number of unordered// coprime pairs of integers from 1 to N#include <bits/stdc++.h>using namespace std;#define N 100005// to store euler's totient functionint phi[N];// to store required answerint S[N];// Computes and prints totient of all numbers// smaller than or equal to N.void computeTotient(){ // Initialise the phi[] with 1 for (int i = 1; i < N; i++) phi[i] = i; // Compute other Phi values for (int p = 2; p < N; p++) { // If phi[p] is not computed already, // then number p is prime if (phi[p] == p) { // Phi of a prime number p is // always equal to p-1. phi[p] = p - 1; // Update phi values of all // multiples of p for (int i = 2 * p; i < N; i += p) { // Add contribution of p to its // multiple i by multiplying with // (1 - 1/p) phi[i] = (phi[i] / p) * (p - 1); } } }}// function to compute number coprime pairsvoid CoPrimes(){ // function call to compute // euler totient function computeTotient(); // prefix sum of all euler totient function values for (int i = 1; i < N; i++) S[i] = S[i - 1] + phi[i];}// Driver codeint main(){ // function call CoPrimes(); int q[] = { 3, 4 }; int n = sizeof(q) / sizeof(q[0]); for (int i = 0; i < n; i++) cout << "Number of unordered coprime\n" << "pairs of integers from 1 to " << q[i] << " are " << S[q[i]] << endl; return 0;} |
C
// C program to find number of unordered// coprime pairs of integers from 1 to N#include <stdio.h>#define N 100005// to store euler's totient functionint phi[N];// to store required answerint S[N];// Computes and prints totient of all numbers// smaller than or equal to N.void computeTotient(){ // Initialise the phi[] with 1 for (int i = 1; i < N; i++) phi[i] = i; // Compute other Phi values for (int p = 2; p < N; p++) { // If phi[p] is not computed already, // then number p is prime if (phi[p] == p) { // Phi of a prime number p is // always equal to p-1. phi[p] = p - 1; // Update phi values of all // multiples of p for (int i = 2 * p; i < N; i += p) { // Add contribution of p to its // multiple i by multiplying with // (1 - 1/p) phi[i] = (phi[i] / p) * (p - 1); } } }}// function to compute number coprime pairsvoid CoPrimes(){ // function call to compute // euler totient function computeTotient(); // prefix sum of all euler totient function values for (int i = 1; i < N; i++) S[i] = S[i - 1] + phi[i];}// Driver codeint main(){ // function call CoPrimes(); int q[] = { 3, 4 }; int n = sizeof(q) / sizeof(q[0]); for (int i = 0; i < n; i++) printf("Number of unordered coprime\npairs of integers from 1 to %d are %d\n",q[i],S[q[i]]); return 0;}// This code is contributed by kothavvsaakash. |
Java
// Java program to find number of unordered// coprime pairs of integers from 1 to Nimport java.util.*;import java.lang.*;import java.io.*;class GFG{static final int N = 100005;// to store euler's// totient functionstatic int[] phi;// to store required answerstatic int[] S ;// Computes and prints totient // of all numbers smaller than// or equal to N.static void computeTotient(){ // Initialise the phi[] with 1 for (int i = 1; i < N; i++) phi[i] = i; // Compute other Phi values for (int p = 2; p < N; p++) { // If phi[p] is not computed // already, then number p is prime if (phi[p] == p) { // Phi of a prime number p // is always equal to p-1. phi[p] = p - 1; // Update phi values of // all multiples of p for (int i = 2 * p; i < N; i += p) { // Add contribution of p to // its multiple i by multiplying // with (1 - 1/p) phi[i] = (phi[i] / p) * (p - 1); } } }}// function to compute// number coprime pairsstatic void CoPrimes(){ // function call to compute // euler totient function computeTotient(); // prefix sum of all euler // totient function values for (int i = 1; i < N; i++) S[i] = S[i - 1] + phi[i];}// Driver codepublic static void main(String args[]){ phi = new int[N]; S = new int[N]; // function call CoPrimes(); int q[] = { 3, 4 }; int n = q.length; for (int i = 0; i < n; i++) System.out.println("Number of unordered coprime\n" + "pairs of integers from 1 to " + q[i] + " are " + S[q[i]] );}}// This code is contributed // by Subhadeep |
Python 3
# Python3 program to find number # of unordered coprime pairs of# integers from 1 to NN = 100005# to store euler's totient functionphi = [0] * N# to store required answerS = [0] * N# Computes and prints totient of all # numbers smaller than or equal to N.def computeTotient(): # Initialise the phi[] with 1 for i in range(1, N): phi[i] = i # Compute other Phi values for p in range(2, N) : # If phi[p] is not computed already, # then number p is prime if (phi[p] == p) : # Phi of a prime number p # is always equal to p-1. phi[p] = p - 1 # Update phi values of all # multiples of p for i in range(2 * p, N, p) : # Add contribution of p to its # multiple i by multiplying with # (1 - 1/p) phi[i] = (phi[i] // p) * (p - 1)# function to compute number # coprime pairsdef CoPrimes(): # function call to compute # euler totient function computeTotient() # prefix sum of all euler # totient function values for i in range(1, N): S[i] = S[i - 1] + phi[i]# Driver codeif __name__ == "__main__": # function call CoPrimes() q = [ 3, 4 ] n = len(q) for i in range(n): print("Number of unordered coprime\n" + "pairs of integers from 1 to ", q[i], " are " , S[q[i]])# This code is contributed # by ChitraNayal |
C#
// C# program to find number // of unordered coprime pairs // of integers from 1 to Nusing System;class GFG{static int N = 100005;// to store euler's// totient functionstatic int[] phi;// to store required answerstatic int[] S ;// Computes and prints totient // of all numbers smaller than// or equal to N.static void computeTotient(){ // Initialise the phi[] with 1 for (int i = 1; i < N; i++) phi[i] = i; // Compute other Phi values for (int p = 2; p < N; p++) { // If phi[p] is not computed // already, then number p is prime if (phi[p] == p) { // Phi of a prime number p // is always equal to p-1. phi[p] = p - 1; // Update phi values of // all multiples of p for (int i = 2 * p; i < N; i += p) { // Add contribution of // p to its multiple i // by multiplying // with (1 - 1/p) phi[i] = (phi[i] / p) * (p - 1); } } }}// function to compute// number coprime pairsstatic void CoPrimes(){ // function call to compute // euler totient function computeTotient(); // prefix sum of all euler // totient function values for (int i = 1; i < N; i++) S[i] = S[i - 1] + phi[i];}// Driver codepublic static void Main(){ phi = new int[N]; S = new int[N]; // function call CoPrimes(); int[] q = { 3, 4 }; int n = q.Length; for (int i = 0; i < n; i++) Console.WriteLine("Number of unordered coprime\n" + "pairs of integers from 1 to " + q[i] + " are " + S[q[i]] );}}// This code is contributed // by mits |
PHP
<?php// PHP program to find number // of unordered coprime pairs// of integers from 1 to N$N = 100005;// to store euler's totient function$phi = array_fill(0, $N, 0);// to store required answer$S = array_fill(0, $N, 0);// Computes and prints totient // of all numbers smaller than// or equal to N.function computeTotient(){ global $N, $phi, $S; // Initialise the phi[] with 1 for ($i = 1; $i < $N; $i++) $phi[$i] = $i; // Compute other Phi values for ($p = 2; $p < $N; $p++) { // If phi[p] is not computed // already, then number p // is prime if ($phi[$p] == $p) { // Phi of a prime number p // is always equal to p-1. $phi[$p] = $p - 1; // Update phi values of // all multiples of p for ($i = 2 * $p; $i < $N; $i += $p) { // Add contribution of p // to its multiple i by // multiplying with (1 - 1/p) $phi[$i] = (int)(($phi[$i] / $p) * ($p - 1)); } } }}// function to compute// number coprime pairsfunction CoPrimes(){ global $N, $phi, $S; // function call to compute // euler totient function computeTotient(); // prefix sum of all euler // totient function values for ($i = 1; $i < $N; $i++) $S[$i] = $S[$i - 1] + $phi[$i];}// Driver code// function callCoPrimes();$q = array( 3, 4 );$n = sizeof($q);for ($i = 0; $i < $n; $i++) echo "Number of unordered coprime\n" . "pairs of integers from 1 to " . $q[$i] . " are ".$S[$q[$i]]."\n";// This code is contributed // by mits?> |
Javascript
<script>// Javascript program to find number of unordered// coprime pairs of integers from 1 to N let N = 100005; // to store euler's // totient function let phi = new Array(N); // to store required answer let S = new Array(N); for(let i = 0; i < N; i++) { phi[i] = 0; S[i] = 0; } // Computes and prints totient // of all numbers smaller than // or equal to N. function computeTotient() { // Initialise the phi[] with 1 for (let i = 1; i < N; i++) phi[i] = i; // Compute other Phi values for (let p = 2; p < N; p++) { // If phi[p] is not computed // already, then number p is prime if (phi[p] == p) { // Phi of a prime number p // is always equal to p-1. phi[p] = p - 1; // Update phi values of // all multiples of p for (let i = 2 * p; i < N; i += p) { // Add contribution of p to // its multiple i by multiplying // with (1 - 1/p) phi[i] = (phi[i] / p) * (p - 1); } } } } // function to compute // number coprime pairs function CoPrimes() { // function call to compute // euler totient function computeTotient(); // prefix sum of all euler // totient function values for (let i = 1; i < N; i++) S[i] = S[i - 1] + phi[i]; } // Driver code // function call CoPrimes(); let q = [ 3, 4 ]; let n = q.length; for (let i = 0; i < n; i++) document.write("Number of unordered coprime<br>" + "pairs of integers from 1 to " + q[i] + " are " + S[q[i]] +"<br>" ); // This code is contributed by avanitrachhadiya2155</script> |
Output:
Number of unordered coprime pairs of integers from 1 to 3 are 4 Number of unordered coprime pairs of integers from 1 to 4 are 6
Time Complexity: O(n + 1000053/2)
Auxiliary Space: O(100005)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
