//java solution with comments
//hope it helps
package ccdec20;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;
public class GBPrimes {
public static void main(String[] args)throws Exception
{
//importing io functions
BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
PrintWriter out = new PrintWriter(System.out);
StringTokenizer st= new StringTokenizer(br.readLine());
//this is number of test cases
int tc=Integer.parseInt(st.nextToken());
//here we store all numbers if prime[i] = 1 then not prime
int primes[]=new int[1000000+2];
primes[0]=1;
primes[1]=1;
//set all multiples of 2 to be not prime
for (int j = 4; j < primes.length; j+=2) {
primes[j]=1;
}
//checking using 3 to sqrt max limit numbers(only odd) and setting all multiples to be 1
//ie not prime
//note were checking from square of n e.g for 3 we start from 9 and increment 2*3 ie 6
//small optimization as 9+3(read odd + odd is even which we already have marked as 1)
//so we increment by 2*i and start from i^2
for (int i = 3; i <= 1000; i+=2) {
for (int j = i*i; j < primes.length; j+=(2*i)) {
primes[j]=1;
}
}
//this is precomputation array...we save count
int count[]=new int[1000000+2];
//during first iternation we check if given count[i] wiz b is prime, if is we check two ahead
//and if it is we simple set count of that index as 1
for (int i = 3; i < count.length; i++)
{
if (primes[i]==1)
continue;
if(i+2<count.length)
if (primes[i+2]==0)
count[i+2]=1;
}
//this loop gives sum of all possible answers upto that index
for (int i = 1; i < count.length; i++) {
count[i]=count[i]+count[i-1];
}
//loop for doing coding
while(tc-->0)
{
int n=Integer.parseInt(br.readLine());
out.println(count[n]);
}
out.flush();
}
}
1 Like
Your approach is wrong, since you are calculating the primes for EVERY TEST CASE, which means your code WILL get TLE. So to avoid it, precompute the primes and store it in array, then answer queries. I’ve posted my solution for your reference.