Count of integers up to N which are non divisors and non coprime with N

Last Updated : 02 Dec, 2021

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 conditions
int 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 Code
int 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 conditions
public 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 conditions
def 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# program to implement 
// the above approach 
using System;

class GFG{
    
// Function to return the count 
// of integers less than N 
// satisfying given conditions
public 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 conditions
function 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:

Time Complexity: O(N*log(log(N)))
Auxiliary Space: O(N)

Find the number of primitive roots modulo prime

grand_master

Improve

Article Tags :

Practice Tags :

Count of integers up to N which are non divisors and non coprime with N

Similar Reads

Thank You!

What kind of Experience do you want to share?