Find difference between count of Prime and Composite in given Range
Given two integers L and R, the task is to find the value of (number of composites – number of primes) that lie in the range [L, R].
Note: 1 is considered neither a prime nor a composite number.
Examples:
Input: L = 2, R = 10
Output: 1
Explanation: The composite numbers in the range are 4, 6, 8, 9, 10 and the prime numbers are 2, 3, 5, 7. So the output is 1.Input: L = 4, R = 5
Output: 0
Approach: The problem can be solved by using the following idea:
Find the count of primes and the count of composites within the given range and then find the difference.
Follow the steps mentioned below to implement the idea:
- Traverse from i = L to R:
- Traverse from j = 2 to the square root of the i.
- If i is divisible by j, then it is not a prime number. So increment the count of composite numbers.
- Otherwise, increment the count of prime numbers.
- Traverse from j = 2 to the square root of the i.
- Return the difference as the required answer.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Function to find the required difference int findDiff( int L, int R) { int prime = 0, comp = 0; bool flag; // Loop to iterate from L to R for ( int i = L; i <= R; i++) { flag = false ; // Loop to check if i is prime for ( int j = 2; j <= sqrt (i); j++) { if (i % j == 0) { flag = true ; break ; } } if (flag) comp++; else prime++; } // Return the difference return comp - prime; } // Driver code int main() { int L = 2, R = 10; // Function call cout << findDiff(L, R); return 0; } |
Java
// Java code to implement the approach import java.io.*; class GFG { // Function to find the required difference public static int findDiff( int L, int R) { int prime = 0 , comp = 0 ; boolean flag = true ; // Loop to iterate from L to R for ( int i = L; i <= R; i++) { flag = false ; // Loop to check if i is prime for ( int j = 2 ; j <= Math.sqrt(i); j++) { if (i % j == 0 ) { flag = true ; break ; } } if (flag == true ) comp++; else prime++; } // Return the difference return comp - prime; } // Driver Code public static void main(String[] args) { int L = 2 , R = 10 ; // Function call System.out.print(findDiff(L, R)); } } // This code is contributed by Rohit Pradhan |
Python3
# Python code to implement the approach import math # Function to find the required difference def findDiff(L, R): prime = 0 comp = 0 flag = True # Loop to iterate from L to R for i in range (L, R + 1 ): flag = False # Loop to check if i is prime for j in range ( 2 ,( int )(math.sqrt(i)) + 1 ): if (i % j = = 0 ): flag = True break if (flag): comp = comp + 1 else : prime = prime + 1 # Return the difference return comp - prime # Driver code L = 2 R = 10 # Function call print (findDiff(L, R)) # This code is contributed by Pushpesh Raj. |
C#
// C# code to implement the approach using System; class GFG { // Function to find the required difference static int findDiff( int L, int R) { int prime = 0, comp = 0; bool flag = true ; // Loop to iterate from L to R for ( int i = L; i <= R; i++) { flag = false ; // Loop to check if i is prime for ( int j = 2; j <= Math.Sqrt(i); j++) { if (i % j == 0) { flag = true ; break ; } } if (flag) comp++; else prime++; } // Return the difference return comp - prime; } // Driver code public static void Main() { int L = 2, R = 10; // Function call Console.Write(findDiff(L, R)); } } // This code is contributed by Samim Hossain Mondal. |
Javascript
// JavaScript code to implement the approach // Function to find the required difference const findDiff = (L, R) => { let prime = 0, comp = 0; let flag; // Loop to iterate from L to R for (let i = L; i <= R; i++) { flag = false ; // Loop to check if i is prime for (let j = 2; j <= parseInt(Math.sqrt(i)); j++) { if (i % j == 0) { flag = true ; break ; } } if (flag) comp++; else prime++; } // Return the difference return comp - prime; } // Driver code let L = 2, R = 10; // Function call console.log(findDiff(L, R)); // This code is contributed by rakeshsahni. |
Output
1
Time Complexity: O((R-L) * sqrt( R))
Auxiliary Space: O(1)
Contact Us