Requirement primes numbers which do not have digit 1 in it.
Input
The first line contains T, the number of test cases. Followed by T lines each contain two numbers M and N
Output
For every test case print the total count of prime numbers which does not contain 1 as a digit.
If all prime number with digit 1 between M and N(Inclusive). then print -1.
Separate the answers for each test case by an empty line.
Constraints
1<=T<=10000 1<=M<=N<=1000000
My code:
final static int MAX = 1000001;
final static int BASE = 10;
final static boolean[] isPrime = generatePrime();
public static void main(String args[] ) throws Exception {
BufferedReader reader = new BufferedReader(new InputStreamReader(
System.in));
int noOfTestCaseT = Integer.parseInt(reader.readLine().trim());
StringBuilder output = new StringBuilder(noOfTestCaseT);
while (noOfTestCaseT != 0) {
noOfTestCaseT--;
String[] tempInt = reader.readLine().split(" ");
int n = Integer.parseInt(tempInt[0].trim());
int m = Integer.parseInt(tempInt[1].trim());
int primesWithoutOnes = getPrimesWithoutOneCount(n, m);
output.append(primesWithoutOnes);
output.append("\n");
}
System.out.println(output);
}
private static int getPrimesWithoutOneCount(int n, int m) {
int totalCount = 0;
for ( int i = n ; i <= m ; i++){
if(isPrime[i] && ! isDigitOnePresent(i) ){
totalCount++;
}
}
if (totalCount == 0) totalCount = -1;
return totalCount;
}
private static boolean isDigitOnePresent(int i) {
while(i !=0 ){
int temp = i % BASE;
if( temp == 1)
return true;
i /= BASE;
}
return false;
}
private static boolean[] generatePrime() {
int root = (int) Math.sqrt(MAX);
boolean[] isPrime = new boolean[MAX];
Arrays.fill(isPrime, true);
isPrime[0] = false; isPrime[1] = false;
for (int i = 0; i < root; i++) {
if (isPrime[i]) {
for (int j = i * i ; j < MAX; j = j + i) {
isPrime[j] = false;
}
}
}
return isPrime;
}
While the code is giving the desired output, it's taking around 2.6 sec for all inputs combined. While the desired time limit is 1 sec(s) for all input files combined. What are the various way I can optimize it in Java?
(I tried with the Sieve of Sundaram but was not able to reduce the time too much).
Submission and all inputs given with time taken for various inputs
1
s in than primes wouldn't it make sense to check that first? \$\endgroup\$1
first, then check the primality of each. \$\endgroup\$