Given a positive integer N, the task is to find the number of positive integers whose GCD with the given integer N is the number itself.
Examples:
Input: N = 5
Output: 2
Explanation:
Following are the numbers whose GCD with N is the number itself:
- Number 1: GCD(1, 5) = 1.
- Number 1: GCD(5, 5) = 5.
Therefore, the total count is 2.
Input: N = 10
Output: 4
Approach: The given problem can be solved based on the observation that the necessary condition for GCD of any number(say K) with N is K if and only if K is a factor of N. Therefore, the idea is to find the number of factors of N. Follow the below steps to solve the problem:
- Initialize a variable, say count as 0, to count the number of factors of N.
- Iterate over the range [1, sqrt(N)] and perform the following steps:
- If the current number i divides the given integer N, then increment count by 1.
- If the value of i and N / i is not the same, then increment count by 1.
- After completing the above steps, print the value of count as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to count numbers whose// GCD with N is the number itselfint countNumbers(int N){ // Stores the count of factors of N int count = 0; // Iterate over the range [1, sqrt(N)] for (int i = 1; i * i <= N; i++) { // If i is divisible by i if (N % i == 0) { // Increment count count++; // Avoid counting the // same factor twice if (N / i != i) { count++; } } } // Return the resultant count return count;}// Driver Codeint main(){ int N = 10; cout << countNumbers(N); return 0;} |
Java
// java program for the above approachimport java.io.*;import java.lang.*;import java.util.*;public class GFG { // Function to count numbers whose // GCD with N is the number itself static int countNumbers(int N) { // Stores the count of factors of N int count = 0; // Iterate over the range [1, sqrt(N)] for (int i = 1; i * i <= N; i++) { // If i is divisible by i if (N % i == 0) { // Increment count count++; // Avoid counting the // same factor twice if (N / i != i) { count++; } } } // Return the resultant count return count; } // Driver Code public static void main(String[] args) { int N = 10; System.out.println(countNumbers(N)); }}// This code is contributed by Kingash. |
Python3
# Python3 program for the above approach# Function to count numbers whose# GCD with N is the number itselfdef countNumbers(N): # Stores the count of factors of N count = 0 # Iterate over the range [1, sqrt(N)] for i in range(1, N + 1): if i * i > N: break # If i is divisible by i if (N % i == 0): # Increment count count += 1 # Avoid counting the # same factor twice if (N // i != i): count += 1 # Return the resultant count return count# Driver Codeif __name__ == '__main__': N = 10 print(countNumbers(N))# This code is contributed by mohit kumar 29 |
C#
// C# program for the above approachusing System;public class GFG { // Function to count numbers whose // GCD with N is the number itself static int countNumbers(int N) { // Stores the count of factors of N int count = 0; // Iterate over the range [1, sqrt(N)] for (int i = 1; i * i <= N; i++) { // If i is divisible by i if (N % i == 0) { // Increment count count++; // Avoid counting the // same factor twice if (N / i != i) { count++; } } } // Return the resultant count return count; } // Driver Code public static void Main(string[] args) { int N = 10; Console.WriteLine(countNumbers(N)); }}// This code is contributed by ukasp. |
Javascript
<script>// Javascript program for the above approach// Function to count numbers whose// GCD with N is the number itselffunction countNumbers(N){ // Stores the count of factors of N var count = 0; // Iterate over the range [1, sqrt(N)] for (i = 1; i * i <= N; i++) { // If i is divisible by i if (N % i == 0) { // Increment count count++; // Avoid counting the // same factor twice if (parseInt(N / i) != i) { count++; } } } // Return the resultant count return count;}// Driver Codevar N = 10;document.write(countNumbers(N));// This code is contributed by Amit Katiyar </script> |
Output:
4
Time Complexity: O(N1/2)
Auxiliary Space: O(1), since N extra space has been taken.
