Given an integer N, the task is to find the count of all possible integers less than N satisfying the following properties:
- The number is not coprime with N i.e their GCD is greater than 1.
- The number is not a divisor of N.
Examples:
Input: N = 10
Output: 3
Explanation:
All possible integers which are less than 10 and are neither divisors nor coprime with 10, are {4, 6, 8}.
Therefore, the required count is 3.
Input: N = 42
Output: 23
Approach:
Follow the steps below to solve the problem:
- Set count = N.
- Calculate Euler’s Totient function for all values up to N to find the count of numbers in the range [1, N] that are coprime to N, i.e., the numbers whose GCD (Greatest Common Divisor) with N is 1.
- Since these are coprime with N, subtract them from the count.
- Calculate the count of divisors of N using Sieve of Eratosthenes. Subtract them from count.
- Print the final value of count which is equal to:
Total count = N – Euler’s totient(N) – Divisor count(N)
Below is the implementation of the above approach:
C++
// C++ Program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to return the count// of integers less than N// satisfying given conditionsint count(int n){ // Stores Euler counts int phi[n + 1] = { 0 }; // Store Divisor counts int divs[n + 1] = { 0 }; // Based on Sieve of Eratosthenes for (int i = 1; i <= n; i++) { phi[i] += i; // Update phi values of all // multiples of i for (int j = i * 2; j <= n; j += i) phi[j] -= phi[i]; // Update count of divisors for (int j = i; j <= n; j += i) divs[j]++; } // Return the final count return (n - phi[n] - divs[n] + 1);}// Driver Codeint main(){ int N = 42; cout << count(N); return 0;} |
Java
// Java program to implement // the above approach import java.util.Arrays;class GFG{ // Function to return the count // of integers less than N // satisfying given conditionspublic static int count(int n) { // Stores Euler counts int []phi = new int[n + 1]; Arrays.fill(phi, 0); // Store Divisor counts int []divs = new int[n + 1]; Arrays.fill(divs, 0); // Based on Sieve of Eratosthenes for(int i = 1; i <= n; i++) { phi[i] += i; // Update phi values of all // multiples of i for(int j = i * 2; j <= n; j += i) phi[j] -= phi[i]; // Update count of divisors for(int j = i; j <= n; j += i) divs[j]++; } // Return the final count return (n - phi[n] - divs[n] + 1); } // Driver Code public static void main(String []args) { int N = 42; System.out.println(count(N)); } }// This code is contributed by grand_master |
Python3
# Python3 program to implement# the above approach# Function to return the count# of integers less than N# satisfying given conditionsdef count(n): # Stores Euler counts phi = [0] * (n + 1) # Store Divisor counts divs = [0] * (n + 1) # Based on Sieve of Eratosthenes for i in range(1, n + 1): phi[i] += i # Update phi values of all # multiples of i for j in range(i * 2, n + 1, i): phi[j] -= phi[i]; # Update count of divisors for j in range(i, n + 1, i): divs[j] += 1 # Return the final count return (n - phi[n] - divs[n] + 1); # Driver code if __name__ == '__main__': N = 42 print(count(N))# This code is contributed by jana_sayantan |
C#
// C# program to implement // the above approach using System;class GFG{ // Function to return the count // of integers less than N // satisfying given conditionspublic static int count(int n) { // Stores Euler counts int []phi = new int[n + 1]; // Store Divisor counts int []divs = new int[n + 1]; // Based on Sieve of Eratosthenes for(int i = 1; i <= n; i++) { phi[i] += i; // Update phi values of all // multiples of i for(int j = i * 2; j <= n; j += i) phi[j] -= phi[i]; // Update count of divisors for(int j = i; j <= n; j += i) divs[j]++; } // Return the final count return (n - phi[n] - divs[n] + 1); } // Driver Code public static void Main(String []args) { int N = 42; Console.WriteLine(count(N)); } }// This code is contributed by 29AjayKumar |
Javascript
<script>// JavaScript implementation of the above approach// Function to return the count // of integers less than N // satisfying given conditionsfunction count(n) { // Stores Euler counts let phi = []; // Store Divisor counts let divs = []; for(let i = 1; i <= n; i++) { phi[i] = 0; divs[i] = 0; } // Based on Sieve of Eratosthenes for(let i = 1; i <= n; i++) { phi[i] += i; // Update phi values of all // multiples of i for(let j = i * 2; j <= n; j += i) phi[j] -= phi[i]; // Update count of divisors for(let j = i; j <= n; j += i) divs[j]++; } // Return the final count return (n - phi[n] - divs[n] + 1); } // Driver code let N = 42; document.write(count(N)); // This code is contributed by code_hunt.</script> |
Output:
23
Time Complexity: O(N*log(log(N)))
Auxiliary Space: O(N)
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!