Primes Without 1's

Question

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

Answer 1

Java is handicapped at HackerEarth

I think that you are handicapped by the fact that Java submissions appear to have a lot higher overhead than C submissions at your HackerEarth site. I checked the submissions for that problem and no one who used Java had a passing time. Then I checked a passing C++ submission and it used the same algorithm as yours. However, you might still be able to beat the requirement if you make some optimizations.

Don't find all primes

Instead of finding primes to MAX every time, you should read the whole input and find out the maximum m value in the input. Then generate only primes up to the maximum m. Many of the input files only requested primes up to 10000 or so.

Also, you can speed up both your prime generating function and your prime counting function by only checking odd numbers.

Rule out the numbers containing 1 once

Currently, you generate all the primes and then for each (n,m) pair, you search the primes list and rule out primes containing the digit 1. Instead of doing it this way, you should:

1. Generate the primes.
2. Iterate through all the primes and rule out primes containing the digit 1 by setting isPrime[i] = false for any prime containing the digit 1.
3. For each (n,m) pair, count the number of primes using isPrime[i] without having to check for the digit 1 again.

This way, you will only check each prime for the digit 1 once instead of once per range.

Finding counts for ranges in O(1) time

Since your input contains many ranges to check, you can make an array to keep track of the cumulative prime count up to each number. Once you generate this array, you can find the count for each (n,m) range in \$O(1)\$ time by just doing:

count = cumulativeCount[m] - cumulativeCount[n-1];

The final program

Here is the program with all the changes. Note that with Java, I couldn't get the runtime below 0.14 seconds even when I removed everything but the parsing code. With an equivalent C program, the runtime was 0.03 seconds. This was using one of the large input files with 5000 test cases.

import java.util.Arrays;
import java.lang.StringBuilder;
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class p4 {
    final static int BASE = 10;
    static boolean[] isPrime;

    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);
        int [][] testCases = new int[noOfTestCaseT][2];
        int maxNum = 0;

        for (int i=0;i<noOfTestCaseT;i++) {
            String[] tempInt = reader.readLine().split(" ");
            testCases[i][0] = Integer.parseInt(tempInt[0].trim());
            testCases[i][1] = Integer.parseInt(tempInt[1].trim());
            if (testCases[i][1] > maxNum)
                maxNum = testCases[i][1];
        }

        isPrime = generatePrime(maxNum+1);

        int [] cumulativeCount = new int[maxNum+1];
        int count = 1;
        cumulativeCount[2] = 1;
        for (int i=3;i<=maxNum;i++) {
            if (((i&1) == 1) && isPrime[i] && !isDigitOnePresent(i))
                count++;
            cumulativeCount[i] = count;
        }

        for (int i=0;i<noOfTestCaseT;i++) {
            int n = testCases[i][0];
            int m = testCases[i][1];
            if (n > 0)
                n--;
            int primesWithoutOnes = cumulativeCount[m] - cumulativeCount[n];
            if (primesWithoutOnes == 0) {
                output.append("-1\n");
            } else {
                output.append(primesWithoutOnes);
                output.append("\n");
            }
        }
        System.out.print(output);
    }

    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 maxNum) {
        int root = (int) Math.sqrt(maxNum) + 1;
        boolean[] isPrime = new boolean[maxNum];
        Arrays.fill(isPrime, true);
        isPrime[0] = false; isPrime[1] = false;
        for (int i = 3; i < root; i+=2) {
            if (isPrime[i]) {
                int increment = i+i;
                for (int j = i * i ; j < maxNum; j = j + increment) {
                    isPrime[j] = false;
                }
            }
        }
        return isPrime;
    }
}

Bonus code

I have each iteration of the program here at Github, so you can test each improvement one by one. I also have a C equivalent of the final program as well.

As a special bonus, I also implemented the cumulative count idea using a binary indexed tree, although that was probably less efficient than using a simple array. It's an interesting data structure though, which is often useful when you need to track cumulative counts.

Answer 2

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.

Answer 3

From my perspective, the biggest issue is the loop inside the getPrimesWithoutOneCount call. This makes your complexity significant.

With a little more pre-processing, you can do a much better log(n) lookup later on. If you extend your preprocessing with:

private static final int[] oneless = getOnelessPrimes();

private static final int[] getOnelessPrimes() {
   int[] oneless = new int[isPrime.length];
   int size = 0;
   for (int i = 0; i < isPrime.length; i++) {
       if (isPrime[i] && !isDigitOnePresent(i)) {
           oneless[size++] = i;
       }
   }
   return Arrays.copyOf(oneless, 0, size);
}

That returns an array of prime values that have no 1 in them.

Now, when you are looking for the count of primes... you can:

int left = Arrays.binarySearch(oneless, first);
if (left < 0) {
    left = -left - 1;
}
int right = Arrays.binarySearch(oneless, left, oneless.length, last);
if (right < 0) {
    right = -right - 1 - 1;
}

int count = right < left ? -1 : (right - left + 1);

That makes your search a lot faster, especially in cases where the difference between M and N is large... e.g. for you, find the number of 1-less primes between 1 and 1000000 would require a lot of iteration. For the above algorithm, though it would require just a little.

Answer 4

It doesn't appear that you use BASE anywhere else in the code other than inside your isDigitOnePresent method, personally I would create that variable inside that method, but that is just my opinion.

Answer 5

As @OldCurmudgeon said, I'd consider eliminating all numbers containing the digit 1 first, then check the primality of each. Also, don't iterate through each number, that's inefficient.

Example: The number 10000 contains a one. Since it is the first digit that is a one, you know that the next 9999 numbers also contain a one, so you can eliminate those immediately.

Do this elimination process in much faster time by simply eliminating the numbers based on the most significant digit that is a 1. At least do the first group (largest) ranges as that will save lots of time. If you don't eliminate every number with a one this way, you can still use the function you already have for the numbers you didn't eliminate this way.

This saves thousands of iterations at best!

First digit is 1:

• 1,
• 10-19, 100-199, 1000-1999, 10000-19999,

Second digit is 1:

• 21, 210-219, 2100-2199, 21000-21999
• 31, 310-319, ...
• ...
• 91, 910-919, ...

Third digit is 1:

• 201, 2010-2019, 20100-20199
• ...

Answer 6

It's unclear why you're using a StringBuilder in main rather than just printing as you go. Printing as you go is more responsive and easier to write, so it seems the obvious choice.

You do no checking for validity on the input. This is fine for the example, but a bad idea if the code is actually meant to be used.

Instead of counting down the number of test cases, it's cannonical to count up the number seen. Plus, why noOfTestCaseT? What's the T mean? Why include the Of? I'd also use num instead of no to prevent ambiguity with the word "no".

Your String[] tempInt = reader.readLine().split(" "); won't work for leading or multiple spaces, although you look like you want it to. Perhaps build a Scanner?

To top it off, try low and high instead of n and m and change getPrimesWithoutOneCount to the equally descriptive but easier to read countPrimeWithoutOnes.

public static void main(String args[] ) throws Exception {
    Scanner reader = new Scanner(System.in);
    int numTestCases = reader.nextInt();

    for (int i = 0; i < numTestCases; i++) {
        int low = reader.nextInt();
        int high = reader.nextInt();

        System.out.println(countPrimeWithoutOnes(low, high));
    }
}

This also allows using nextLine to check that the whole line was used.

countPrimeWithoutOnes needs reformatting. Further, the action

if (totalCount == 0) totalCount = -1;

should not be part of countPrimeWithoutOnes. This is not what the function claims to do! Let main do that, since it's responsible for output.

The whole function can be simplified to

private static int countPrimeWithoutOnes(int low, int high) {
    return (int)IntStream.rangeClosed(low, high)
                         .filter(i -> isPrime[i] && !isDigitOnePresent(i))
                         .count();
}

then, but this is unfortunately way slower in this microbenchmark. I'll leave it as a hypothetical, then.

The problem mostly revolves around having a really large number of inputs, so the overhead from generatePrime is largely insignificant. Other people have explained this already, though, so there's not much point me repeating it.

Answer 7

An alternative, which may be faster (I haven't tested it):

private static boolean isDigitOnePresent(int i) {
    return Integer.toString(i).contains("1");
}

It uses only library methods, and so should be reasonably fast.