Primes Without 1's

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() {

The most obvious culprit for the slowness seems to be that you find all the primes in the maximum allowed range, when in the test file there might be significantly smaller sub-ranges. You could try to change the logic to find primes within ranges on-demand as needed.

A small speed improvement is possible in the way you find if a number contains a 1. You could replace the modulo with checking the last bit using the & operator.

Not related to speed, but many of the names are very tedious. I recommend some renames:

• "getPrimesWithoutOneCount" to "countPrimesWithoutOne"

• "isDigitOnePresent" to "containsOne"

Lastly, the input parsing looks really tedious. You could rewrite using a Scanner elegantly.

StackExchange Code Review Q#93008, answer score: 4