daily pastebin goal
53%
SHARE
TWEET

Untitled

a guest Mar 13th, 2018 94 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.*;
  2. import java.lang.*;
  3.  
  4. class Main
  5. {
  6.     public static void main (String[] args) throws java.lang.Exception
  7.     {
  8.         Scanner scanner = new Scanner(System.in);
  9.         int n = scanner.nextInt();
  10.         int[][] tests = new int[n][2];
  11.         int max = 0;
  12.         for (int i = 0; i < n; i++) {
  13.             tests[i][0] = scanner.nextInt();
  14.             tests[i][1] = scanner.nextInt();
  15.             if (tests[i][1] > max) {
  16.                 max = tests[i][1];
  17.             }
  18.         }
  19.         int[] primes = new int[max + 1];
  20.         for (int i = 2; i < max + 1; i++) {
  21.             primes[i] = 1;
  22.         }
  23.         for (int i = 4; i < max + 1; i += 2) {
  24.             primes[i] = 0;
  25.         }
  26.         for (int i = 3; i <= (max + 1) / 2; i += 6) {
  27.             if (primes[i] == 0) {
  28.                 continue;
  29.             }
  30.             for (int j = 2 * i; j < max + 1; j += i) {
  31.                 primes[j] = 0;
  32.             }
  33.             if (i + 1 < max) {
  34.                 if (primes[i] == 0) {
  35.                     continue;
  36.                 }
  37.                 for (int j = 2 * (i + 2); j < max + 1; j += (i + 2)) {
  38.                     primes[j] = 0;
  39.                 }
  40.             }
  41.         }
  42.         for (int i = 1; i < max + 1; i++) {
  43.             primes[i] += primes[i - 1];
  44.         }
  45.         for (int i = 0; i < n; i++) {
  46.             System.out.println(primes[tests[i][1]] - primes[tests[i][0]]);
  47.         }
  48.     }
  49. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top