Given this as a the Problem Statement
Given two numbers, find the sum of prime numbers between them, both inclusive.
Input:
The first line contains the number of test cases T. Each test case contains two space separated integers.
Output:
Print the answer on a new line for each case.
Constraints:
1 <= T <= 100
1 <= a,b < 10^6
. Here is the working code of mine, that has been accepted.
class TestClass {
public static void main(String args[] ) throws Exception {
BufferedReader keyboard= new BufferedReader(new InputStreamReader(System.in));
int t=Integer.parseInt(keyboard.readLine());
while(t>0 && t<=100){
String[] tempInt=keyboard.readLine().split(" ");
int n=Integer.parseInt(tempInt[0]);
int m=Integer.parseInt(tempInt[1]);
int sum=primeSum(n,m);
System.out.println(sum);
t--;
}
}
private static int primeSum(int n, int m) {
int sum=0;
int maxFactor= (int)Math.sqrt(m);
boolean[] isPrime=new boolean[m + 1];
int len=isPrime.length;
Arrays.fill(isPrime,true);
isPrime[0]=false;
isPrime[1]=false;
for(int i=0;i<=maxFactor;i++){
if(isPrime[i]){
for(int j=i+i;j<len;j+=i){
isPrime[j]=false;
}
}
}
for(int i=n;i<=m;i++){
if(isPrime[i]){
sum=sum+i;
}
}
return sum;
}
}
But what is really bugging me is this line boolean[] isPrime=new boolean[m + 1];
. Where i Have to use really large block of space. How could i avoid such large allocation while being effiecient too.? What are futher way of improvement of this code apart from array allocation ?
BitSet
may save some memory(it does not change asymptotic behavior, though). \$\endgroup\$