Given Q queries in the form of 2D array arr[][] whose every row consists of two numbers L and R which denotes the range [L, R], the task is to find the sum of all Composite Numbers lying in range [L, R].
Input: arr[][] = {{10, 13}, {12, 21}}
Output:
22
116
Explanation:
From 10 to 13 only 10 and 12 is the composite number.
From 12 to 21, there are 7 composite numbers
12 + 14 + 15 + 16 + 18 + 20 + 21 = 116
Input: arr[][] = {{ 10, 10 }, { 258, 785 }, {45, 245 }, { 1, 1000}}
Output:
10
233196
23596
424372
Approach:
The idea is to use the prefix sum array. The sum of all composite number till that particular index is precomputed and stored in an array pref[] so that every query can be answered in O(1) time.
- Initialise the prefix array pref[].
- Iterate from 1 to N and check if the number is composite or not:
- If the number is composite then, the current index of pref[] will store the sum of the number and the number at previous index of pref[].
- Else the current index of pref[] is same as the value at previous index of pref[].
- For Q queries the sum of all composite numbers for range [L, R] can be found as follows:
sum = pref[R] - pref[L - 1]
Below is the implementation of the above approach:
C++
// C++ implementation to find the sum// of all composite numbers// in the given range#include <bits/stdc++.h>using namespace std;// Prefix array to precompute// the sum of all composite// numberslong long pref[100001];// Function that return number// num if num is composite// else return 0int isComposite(int n){ // Corner cases if (n <= 1) return 0; if (n <= 3) return 0; // This is checked so that we can skip // middle five numbers in below loop if (n % 2 == 0 || n % 3 == 0) return n; for (int i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return n; return 0;}// Function to precompute the// sum of all Composite numbers// upto 10^5void preCompute(){ for (int i = 1; i <= 100000; ++i) { // isComposite() // return the number i // if i is Composite // else return 0 pref[i] = pref[i - 1] + isComposite(i); }}// Function to print the sum// for each queryvoid printSum(int L, int R){ cout << pref[R] - pref[L - 1] << endl;}// Function to print sum of all// Composite numbers between// [L, R]void printSumComposite(int arr[][2], int Q){ // Function that pre computes // the sum of all Composite // numbers preCompute(); // Iterate over all Queries // to print the sum for (int i = 0; i < Q; i++) { printSum(arr[i][0], arr[i][1]); }}// Driver codeint main(){ // Queries int Q = 2; int arr[][2] = { { 10, 13 }, { 12, 21 } }; // Function that print the // the sum of all composite // number in Range [L, R] printSumComposite(arr, Q); return 0;} |
Java
// Java implementation to find the sum// of all Composite numbers// in the given rangeimport java.util.*;class GFG { // Prefix array to precompute // the sum of all Composite // number static int[] pref = new int[100001]; // Function that return number // num if num is Composite // else return 0 static int isComposite(int n) { // Corner cases if (n <= 1) return 0; if (n <= 3) return 0; // This is checked so that we can skip // middle five numbers in below loop if (n % 2 == 0 || n % 3 == 0) return n; for (int i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return n; return 0; } // Function to precompute the // sum of all Composite numbers // upto 100000 static void preCompute() { for (int i = 1; i <= 100000; ++i) { // checkComposite() // return the number i // if i is Composite // else return 0 pref[i] = pref[i - 1] + isComposite(i); } } // Function to print the sum // for each query static void printSum(int L, int R) { System.out.print(pref[R] - pref[L - 1] + "\n"); } // Function to print sum of all // Composite numbers between // [L, R] static void printSumComposite(int arr[][], int Q) { // Function that pre computes // the sum of all Composite // numbers preCompute(); // Iterate over all Queries // to print the sum for (int i = 0; i < Q; i++) { printSum(arr[i][0], arr[i][1]); } } // Driver code public static void main(String[] args) { // Queries int Q = 2; int arr[][] = { { 10, 13 }, { 12, 21 } }; // Function that print the // the sum of all Composite // number in Range [L, R] printSumComposite(arr, Q); }} |
Python3
# Python implementation to find the sum# of all composite numbers# in the given range# Prefix array to precompute# the sum of all composite# numberpref =[0]*100001# Function that return number# num if num is composite# else return 0def isComposite(n): # Corner cases if (n <= 1): return 0 if (n <= 3): return 0 # This is checked so that we can skip # middle five numbers in below loop if (n % 2 == 0 or n % 3 == 0): return n i = 5 while(i * i <= n): if (n % i == 0 or n % (i + 2) == 0): return n i = i + 6 return 0# Function to precompute the# sum of all composite numbers# upto 100000def preCompute(): for i in range(1, 100001): # checkcomposite() # return the number i # if i is composite # else return 0 pref[i] = pref[i - 1]+ isComposite(i) # Function to print the sum# for each querydef printSum(L, R): print(pref[R] - pref[L - 1])# Function to print sum of all# composite numbers betweendef printSumcomposite(arr, Q): # Function that pre computes # the sum of all composite # numbers preCompute() # Iterate over all Queries # to print the sum for i in range(Q): printSum(arr[i][0], arr[i][1]) # Driver codeif __name__ == "__main__": Q = 2 arr = [[10, 13 ], [ 12, 21 ]] # Function that print the # the sum of all composite # number in Range [L, R] printSumcomposite(arr, Q) |
C#
// C# implementation to find the sum// of all Composite numbers// in the given rangeusing System;public class GFG{// Prefix array to precompute// the sum of all Composite// numberstatic int[] pref = new int[100001];// Function that return number// num if num is Composite// else return 0static int isComposite(int n){ // Corner cases if (n <= 1) return 0; if (n <= 3) return 0; // This is checked so that we can skip // middle five numbers in below loop if (n % 2 == 0 || n % 3 == 0) return n; for(int i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return n; return 0;}// Function to precompute the// sum of all Composite numbers// upto 100000static void preCompute(){ for(int i = 1; i <= 100000; ++i) { // CheckComposite() // return the number i // if i is Composite // else return 0 pref[i] = pref[i - 1] + isComposite(i); }}// Function to print the sum// for each querystatic void printSum(int L, int R){ Console.Write(pref[R] - pref[L - 1] + "\n");}// Function to print sum of all// Composite numbers between// [L, R]static void printSumComposite(int [,]arr, int Q){ // Function that pre computes // the sum of all Composite // numbers preCompute(); // Iterate over all Queries // to print the sum for(int i = 0; i < Q; i++) { printSum(arr[i, 0], arr[i, 1]); }}// Driver codepublic static void Main(String[] args){ // Queries int Q = 2; int [,]arr = { { 10, 13 }, { 12, 21 } }; // Function that print the // the sum of all Composite // number in Range [L, R] printSumComposite(arr, Q);}}// This code is contributed by Princi Singh |
Javascript
<script>// Javascript implementation to find the sum// of all composite numbers// in the given range// Prefix array to precompute// the sum of all composite// numbersvar pref = Array(100001).fill(0);// Function that return number// num if num is composite// else return 0function isComposite( n){ // Corner cases if (n <= 1) return 0; if (n <= 3) return 0; // This is checked so that we can skip // middle five numbers in below loop if (n % 2 == 0 || n % 3 == 0) return n; for (var i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return n; return 0;}// Function to precompute the// sum of all Composite numbers// upto 10^5function preCompute(){ for (var i = 1; i <= 100000; ++i) { // isComposite() // return the number i // if i is Composite // else return 0 pref[i] = pref[i - 1] + isComposite(i); }}// Function to print the sum// for each queryfunction printSum(L, R){ document.write( pref[R] - pref[L - 1] +"<br>");}// Function to print sum of all// Composite numbers between// [L, R]function printSumComposite(arr, Q){ // Function that pre computes // the sum of all Composite // numbers preCompute(); // Iterate over all Queries // to print the sum for (var i = 0; i < Q; i++) { printSum(arr[i][0], arr[i][1]); }}// Driver code// Queriesvar Q = 2;var arr = [ [ 10, 13 ], [ 12, 21 ] ];// Function that print the// the sum of all composite// number in Range [L, R]printSumComposite(arr, Q);</script> |
Output:
22 116
Time Complexity: O(MAX3/2), where MAX = 100000
Auxiliary Space: O(MAX)
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!
