Given an array arr[] of N integers, and a range L to R, the task is to find the total number of elements in the array from index L to R that satisfies the following condition:
where F(x) is Euler’s Totient Function.
![F(arr[i]) = arr[i] - 1](https://neveropen.co.uk/wp-content/uploads/2024/01/wardslaus_quicklatex.com-fac69e679d341663a90f9df9c642ca41_l3-1.png "Rendered by QuickLaTeX.com")
Examples:
Input: arr[] = {2, 4, 5, 8}, L = 1, R = 3
Output: 2
Explanation:
Here in the given range, F(2) = 1 and (2 – 1) = 1. Similarly, F(5) = 4 and (5 – 1) = 4.
So the total count of indices which satisfy the condition is 2.
Input: arr[] = {9, 3, 4, 6, 8}, L = 3, R = 5
Output: 0
Explanation :
In the given range there is no element that satisfies the given condition.
So the total count is 0.
Naive Approach: The naive approach to solve this problem is to iterate over all the elements of the array and check if the Euler’s Totient value of the current element is one less than itself. If yes then increment the count.
Time Complexity: O(N * sqrt(N))
Auxiliary Space: O(1)
Efficient Approach:
Euler’s Totient function F(n) for an input n is the count of numbers in {1, 2, 3, …, n} that are relatively prime to n, i.e., the numbers whose Greatest Common Divisor with n is 1.
- If we observe, we can notice that the above given condition is only satisfied by the Prime numbers.
- So, all we need to do is to compute the total numbers of prime numbers in the given range.
- We will use Sieve of Eratosthenes to compute prime numbers efficiently.
- Also, we will pre-compute the numbers of primes numbers in a count array.
Below is the implementation of the above approach.
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;long long prime[1000001] = { 0 };// Seiev of Erotosthenes method to compute all primesvoid seiveOfEratosthenes(){ for (int i = 2; i < 1000001; i++) prime[i] = 1; for (int i = 2; i * i < 1000001; i++) { // If current number is marked prime then mark its // multiple as non-prime if (prime[i] == 1) for (int j = i * i; j < 1000001; j += i) prime[j] = 0; }}// Function to count the number// of element satisfying the conditionvoid CountElements(int arr[], int n, int L, int R){ seiveOfEratosthenes(); long long countPrime[n + 1] = { 0 }; // Compute the number of primes in count prime array for (int i = 1; i <= n; i++) countPrime[i] = countPrime[i - 1] + prime[arr[i - 1]]; // Print the number of elements satisfying the condition printf("%lld", (countPrime[R] - countPrime[L - 1])); return;}// Driver Codeint main(){ // Given array int arr[] = { 2, 4, 5, 8 }; // Size of the array int N = sizeof(arr) / sizeof(int); int L = 1, R = 3; // Function Call CountElements(arr, N, L, R); return 0;}// This code is contributed by Sania Kumari Gupta |
C
// C program for the above approach#include <stdio.h>#include <string.h>long long prime[1000001];// Seiev of Erotosthenes method to compute all primesvoid seiveOfEratosthenes(){ memset(prime, 0, sizeof(prime)); for (int i = 2; i < 1000001; i++) prime[i] = 1; for (int i = 2; i * i < 1000001; i++) { // If current number is marked prime then mark its // multiple as non-prime if (prime[i] == 1) for (int j = i * i; j < 1000001; j += i) prime[j] = 0; }}// Function to count the number// of element satisfying the conditionvoid CountElements(int arr[], int n, int L, int R){ seiveOfEratosthenes(); long long countPrime[n + 1]; memset(countPrime, 0, sizeof(countPrime)); // Compute the number of primes in count prime array for (int i = 1; i <= n; i++) countPrime[i] = countPrime[i - 1] + prime[arr[i - 1]]; // Print the number of elements satisfying the condition printf("%lld", (countPrime[R] - countPrime[L - 1])); return;}// Driver Codeint main(){ // Given array int arr[] = { 2, 4, 5, 8 }; // Size of the array int N = sizeof(arr) / sizeof(int); int L = 1, R = 3; // Function Call CountElements(arr, N, L, R); return 0;}// This code is contributed by Sania Kumari Gupta |
Java
// Java program for the above approachimport java.util.*;class GFG{static int prime[] = new int[1000001];// Seiev of Erotosthenes method to// compute all primesstatic void seiveOfEratosthenes(){ for(int i = 2; i < 1000001; i++) { prime[i] = 1; } for(int i = 2; i * i < 1000001; i++) { // If current number is // marked prime then mark // its multiple as non-prime if (prime[i] == 1) { for(int j = i * i; j < 1000001; j += i) { prime[j] = 0; } } }}// Function to count the number// of element satisfying the conditionstatic void CountElements(int arr[], int n, int L, int R){ seiveOfEratosthenes(); int countPrime[] = new int[n + 1]; // Compute the number of primes // in count prime array for(int i = 1; i <= n; i++) { countPrime[i] = countPrime[i - 1] + prime[arr[i - 1]]; } // Print the number of elements // satisfying the condition System.out.print(countPrime[R] - countPrime[L - 1] + "\n"); return;}// Driver Codepublic static void main(String[] args){ // Given array int arr[] = { 2, 4, 5, 8 }; // Size of the array int N = arr.length; int L = 1, R = 3; // Function Call CountElements(arr, N, L, R);}}// This code is contributed by amal kumar choubey |
Python3
# Python3 program for the above approachprime = [0] * (1000001)# Seiev of Erotosthenes method to# compute all primesdef seiveOfEratosthenes(): for i in range(2, 1000001): prime[i] = 1 i = 2 while(i * i < 1000001): # If current number is # marked prime then mark # its multiple as non-prime if (prime[i] == 1): for j in range(i * i, 1000001, i): prime[j] = 0 i += 1# Function to count the number# of element satisfying the conditiondef CountElements(arr, n, L, R): seiveOfEratosthenes() countPrime = [0] * (n + 1) # Compute the number of primes # in count prime array for i in range(1, n + 1): countPrime[i] = (countPrime[i - 1] + prime[arr[i - 1]]) # Print the number of elements # satisfying the condition print(countPrime[R] - countPrime[L - 1]) return# Driver Code# Given arrayarr = [ 2, 4, 5, 8 ]# Size of the arrayN = len(arr)L = 1R = 3# Function callCountElements(arr, N, L, R)# This code is contributed by sanjoy_62 |
C#
// C# program for the above approachusing System;class GFG{static int []prime = new int[1000001];// Seiev of Erotosthenes method to// compute all primesstatic void seiveOfEratosthenes(){ for(int i = 2; i < 1000001; i++) { prime[i] = 1; } for(int i = 2; i * i < 1000001; i++) { // If current number is // marked prime then mark // its multiple as non-prime if (prime[i] == 1) { for(int j = i * i; j < 1000001; j += i) { prime[j] = 0; } } }}// Function to count the number// of element satisfying the conditionstatic void CountElements(int []arr, int n, int L, int R){ seiveOfEratosthenes(); int []countPrime = new int[n + 1]; // Compute the number of primes // in count prime array for(int i = 1; i <= n; i++) { countPrime[i] = countPrime[i - 1] + prime[arr[i - 1]]; } // Print the number of elements // satisfying the condition Console.Write(countPrime[R] - countPrime[L - 1] + "\n"); return;}// Driver Codepublic static void Main(String[] args){ // Given array int []arr = { 2, 4, 5, 8 }; // Size of the array int N = arr.Length; int L = 1, R = 3; // Function Call CountElements(arr, N, L, R);}}// This code is contributed by sapnasingh4991 |
Javascript
<script>// JavaScript program for the above approachlet prime = new Uint8Array(1000001);// Seiev of Erotosthenes method to// compute all primesfunction seiveOfEratosthenes(){ for (let i = 2; i < 1000001; i++) { prime[i] = 1; } for (let i = 2; i * i < 1000001; i++) { // If current number is // marked prime then mark // its multiple as non-prime if (prime[i] == 1) { for (let j = i * i; j < 1000001; j += i) { prime[j] = 0; } } }}// Function to count the number// of element satisfying the conditionfunction CountElements(arr, n, L, R){ seiveOfEratosthenes(); countPrime = new Uint8Array(n + 1); // Compute the number of primes // in count prime array for (let i = 1; i <= n; i++) { countPrime[i] = countPrime[i - 1] + prime[arr[i - 1]]; } // Print the number of elements // satisfying the condition document.write((countPrime[R] - countPrime[L - 1]) + "<br>"); return;}// Driver Code // Given array let arr = [ 2, 4, 5, 8 ]; // Size of the array let N = arr.length; let L = 1, R = 3; // Function Call CountElements(arr, N, L, R);// This code is contributed by Surbhi Tyagi.</script> |
Output:
2
Time Complexity: O(N * log(logN))
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!
Share your thoughts in the comments
