Given an integer N, the task is to count the number of integers from the range [1, N] having at least one in common prime factor with N other than 1.
Examples:
Input: N = 5
Output: 1
Explanation:
Since 5 is prime. Therefore, there is no other number which is at most N, that has at least one common factor with N except N itself. Therefore, the count is 1.Input: N = 12
Output: 8
Naive Approach: The simplest approach to solve the given problem is to iterate through all the numbers over the range [1, N], and for every element, if the GCD of each number with N is greater than 1, then increment the count. Otherwise, check for the next number. After checking all the numbers, we print the total count obtained.
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 all the numbers// in the range [1, N] having common// factor with N other than 1int countNumbers(int N){ // Stores the count of numbers // having more than 1 factor with N int count = 0; // Iterate over the range [1, N] for (int i = 1; i <= N; i++) { // If gcd is not 1 then // increment the count if (__gcd(i, N) != 1) count++; } // Print the resultant count cout << count;}// Driver Codeint main(){ int N = 5; countNumbers(N); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to count all the numbers// in the range [1, N] having common// factor with N other than 1static void countNumbers(int N){ // Stores the count of numbers // having more than 1 factor with N int count = 0; // Iterate over the range [1, N] for(int i = 1; i <= N; i++) { // If gcd is not 1 then // increment the count if (__gcd(i, N) != 1) count++; } // Print the resultant count System.out.print(count);}static int __gcd(int a, int b) { return b == 0 ? a : __gcd(b, a % b);}// Driver Codepublic static void main(String[] args) { int N = 5; countNumbers(N);}}// This code is contributed by shikhasingrajput |
Python3
# Python 3 program for the above approachimport math# Function to count all the numbers# in the range [1, N] having common# factor with N other than 1def countNumbers(N): # Stores the count of numbers # having more than 1 factor with N count = 0 # Iterate over the range [1, N] for i in range(1, N + 1): # If gcd is not 1 then # increment the count if (math.gcd(i, N) != 1): count += 1 # Print the resultant count print(count)# Driver Codeif __name__ == "__main__": N = 5 countNumbers(N) # This code is contributed by ukasp. |
C#
// C# program for the above approachusing System;public class GFG{// Function to count all the numbers// in the range [1, N] having common// factor with N other than 1static void countNumbers(int N){ // Stores the count of numbers // having more than 1 factor with N int count = 0; // Iterate over the range [1, N] for(int i = 1; i <= N; i++) { // If gcd is not 1 then // increment the count if (__gcd(i, N) != 1) count++; } // Print the resultant count Console.Write(count);}static int __gcd(int a, int b) { return b == 0 ? a : __gcd(b, a % b);}// Driver Codepublic static void Main(String[] args) { int N = 5; countNumbers(N);}} // This code is contributed by 29AjayKumar |
Javascript
<script>// javascript program for the above approach// Function to count all the numbers// in the range [1, N] having common// factor with N other than 1function countNumbers(N){ // Stores the count of numbers // having more than 1 factor with N var count = 0; // Iterate over the range [1, N] for(var i = 1; i <= N; i++) { // If gcd is not 1 then // increment the count if (__gcd(i, N) != 1) count++; } // Print the resultant count document.write(count);}function __gcd(a , b) { return b == 0 ? a : __gcd(b, a % b);}// Driver Codevar N = 5;countNumbers(N);// This code is contributed by 29AjayKumar </script> |
Output:
1
Time Complexity: O(N*log N)
Auxiliary Space: O(1), since no extra space has been taken.
Efficient Approach: The above approach can also be optimized by using Euler’s totient function which gives the count of numbers less than N having no common prime factor with N. Follow the steps below to solve the problem:
- Initialize a variable, say count that stores the numbers having common prime factors other than 1.
- Define a function, phi() to calculate the value of Euler’s totient function which represents the count of integers less than N having no common factor with N.
- After completing the above steps, print the value of (N – phi(N) as the resultant count.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to calculate the value of// Euler's totient functionint phi(int N){ // Initialize result with N int result = N; // Find all prime factors of N // and subtract their multiples for (int p = 2; p * p <= N; ++p) { // Check if p is a prime factor if (N % p == 0) { // If found to be true, // then update N and result while (N % p == 0) N /= p; result -= result / p; } } // If N has a prime factor greater // than sqrt(N), then there can be // at-most one such prime factor if (N > 1) result -= result / N; return result;}// Function to count all the numbers// in the range [1, N] having common// factor with N other than 1int countNumbers(int N){ // Stores the resultant count int count = N - phi(N); // Print the count cout << count;}// Driver Codeint main(){ int N = 5; countNumbers(N); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG { // Function to calculate the value of// Euler's totient functionstatic int phi(int N){ // Initialize result with N int result = N; // Find all prime factors of N // and subtract their multiples for (int p = 2; p * p <= N; ++p) { // Check if p is a prime factor if (N % p == 0) { // If found to be true, // then update N and result while (N % p == 0) N /= p; result -= result / p; } } // If N has a prime factor greater // than sqrt(N), then there can be // at-most one such prime factor if (N > 1) result -= result / N; return result;}// Function to count all the numbers// in the range [1, N] having common// factor with N other than 1static void countNumbers(int N){ // Stores the resultant count int count = N - phi(N); // Print the count System.out.print(count);} // Driver codepublic static void main (String[] args){ int N = 5; countNumbers(N);}}// This code is contributed by offbeat. |
Python3
# Python3 program for the above approach# Function to calculate the value of# Euler's totient functiondef phi(N): # Initialize result with N result = N # Find all prime factors of N # and subtract their multiples for p in range(2, int(pow(N, 1 / 2)) + 1): # Check if p is a prime factor if (N % p == 0): # If found to be true, # then update N and result while (N % p == 0): N = N / p result -= result // p # If N has a prime factor greater # than sqrt(N), then there can be # at-most one such prime factor if (N > 1): result -= result // N return result# Function to count all the numbers# in the range [1, N] having common# factor with N other than 1def countNumbers(N): # Stores the resultant count count = N - phi(N) # Print the count print(count)# Driver CodeN = 5countNumbers(N)# This code is contributed by SoumikMondal |
C#
// C# program for the above approachusing System;public class GFG { // Function to calculate the value of// Euler's totient functionstatic int phi(int N){ // Initialize result with N int result = N; // Find all prime factors of N // and subtract their multiples for (int p = 2; p * p <= N; ++p) { // Check if p is a prime factor if (N % p == 0) { // If found to be true, // then update N and result while (N % p == 0) N /= p; result -= result / p; } } // If N has a prime factor greater // than sqrt(N), then there can be // at-most one such prime factor if (N > 1) result -= result / N; return result;}// Function to count all the numbers// in the range [1, N] having common// factor with N other than 1static void countNumbers(int N){ // Stores the resultant count int count = N - phi(N); // Print the count Console.Write(count);} // Driver codepublic static void Main(String[] args){ int N = 5; countNumbers(N);}}// This code contributed by shikhasingrajput |
Javascript
<script>// Javascript implementation// for the above approach// Function to calculate the value of// Euler's totient functionfunction phi(N){ // Initialize result with N let result = N; // Find all prime factors of N // and subtract their multiples for (let p = 2; p * p <= N; ++p) { // Check if p is a prime factor if (N % p == 0) { // If found to be true, // then update N and result while (N % p == 0) N /= p; result -= result / p; } } // If N has a prime factor greater // than sqrt(N), then there can be // at-most one such prime factor if (N > 1) result -= result / N; return result;} // Function to count all the numbers// in the range [1, N] having common// factor with N other than 1function countNumbers(N){ // Stores the resultant count let count = N - phi(N); // Print the count document.write(count);}// Driver Code let N = 5; countNumbers(N);// This code is contributed by susmitakundugoaldanga.</script> |
Output:
1
Time Complexity: O(sqrt(N))
Auxiliary Space: O(1)
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!
