fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Ideone
  9. {
  10. 	final static int BASE = 10;
  11.     static boolean[] isPrime;
  12. 	public static void main (String[] args) throws java.lang.Exception
  13. 	{
  14. 	BufferedReader reader = new BufferedReader(new InputStreamReader(
  15.                     System.in));
  16.         int noOfTestCaseT = Integer.parseInt(reader.readLine().trim());
  17.         StringBuilder output = new StringBuilder(noOfTestCaseT);
  18.         int [][] testCases = new int[noOfTestCaseT][2];
  19.         int maxNum = 0;
  20.  
  21.         for (int i=0;i<noOfTestCaseT;i++) {
  22.             String[] tempInt = reader.readLine().split(" ");
  23.             testCases[i][0] = Integer.parseInt(tempInt[0].trim());
  24.             testCases[i][1] = Integer.parseInt(tempInt[1].trim());
  25.             if (testCases[i][1] > maxNum)
  26.                 maxNum = testCases[i][1];
  27.         }
  28.  
  29.         isPrime = generatePrime(maxNum+1);
  30.  
  31.         int [] cumulativeCount = new int[maxNum+1];
  32.         int count = 1;
  33.         cumulativeCount[2] = 1;
  34.         for (int i=3;i<=maxNum;i++) {
  35.             if (((i&1) == 1) && isPrime[i] && !isDigitOnePresent(i))
  36.                 count++;
  37.             cumulativeCount[i] = count;
  38.         }
  39.  
  40.         for (int i=0;i<noOfTestCaseT;i++) {
  41.             int n = testCases[i][0];
  42.             int m = testCases[i][1];
  43.             if (n > 0)
  44.                 n--;
  45.             int primesWithoutOnes = cumulativeCount[m] - cumulativeCount[n];
  46.             if (primesWithoutOnes == 0) {
  47.                 output.append("-1\n");
  48.             } else {
  49.                 output.append(primesWithoutOnes);
  50.                 output.append("\n");
  51.             }
  52.         }
  53.         System.out.print(output);
  54.     }
  55.  
  56.     private static boolean isDigitOnePresent(int i) {
  57.         while(i !=0 ){
  58.             int temp = i % BASE;
  59.             if( temp == 1)
  60.                 return true;
  61.             i /= BASE;
  62.         }
  63.         return false;
  64.     }
  65.  
  66.     private static boolean[] generatePrime(int maxNum) {
  67.         int root = (int) Math.sqrt(maxNum);
  68.         boolean[] isPrime = new boolean[maxNum];
  69.         Arrays.fill(isPrime, true);
  70.         isPrime[0] = false; isPrime[1] = false;
  71.         for (int i = 3; i < root; i+=2) {
  72.             if (isPrime[i]) {
  73.                 int increment = i+i;
  74.                 for (int j = i * i ; j < maxNum; j = j + increment) {
  75.                     isPrime[j] = false;
  76.                 }
  77.             }
  78.         }
  79.         return isPrime;
  80.     }
  81. }
Success #stdin #stdout 0.1s 320320KB
comments (?)
stdin
copy 
1
276 297
stdout
copy 
4
https://ideone.com/dbKicE
language:
Java (HotSpot 12)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!