Problem Statement:
Given a number N, let CP(N) denote the number of primes between 1 and N (inclusive of N). We call N a prime counter if CP(N) is a prime (N need not be a prime).
For example, CP(3) = 2, CP(4) = 2, CP(5) = 2, CP(7) = 4.
Input Format:
First-line contains an integer T, a number of test cases. Next T lines each containing two positive integers L, R separated by space.
Output Format:
T lines containing the number of prime counters between L and R (both inclusive) in the ith test case (or NONE is no prime counter exists in that range).
Constraints:
L ≤ R ≤ 106
Example 1:
Input: 1
1 10
Output: 4
Example 2:
Input: 2
2 20
21 30
Output: 8
NONE
Code
Java
C++
Python
import java.util.*;
import java.io.*;
class Innoskrit {
public static void primeCounters(int ranges[][], int size) {
boolean primeSieve[] = new boolean[size + 1];
Arrays.fill(primeSieve, true);
int cp[] = new int[size + 1];
int primeCounters[] = new int[size + 1];
primeSieve[0] = false;
primeSieve[1] = false;
for(int number = 2; number <= size; number++) {
if(primeSieve[number]) {
cp[number] = cp[number - 1] + 1;
} else {
cp[number] = cp[number - 1];
}
if(primeSieve[cp[number]]) {
primeCounters[number] = primeCounters[number - 1] + 1;
} else {
primeCounters[number] = primeCounters[number - 1];
}
if(primeSieve[number]) {
for(int multiple = number*number; multiple <= size; multiple += number) {
primeSieve[multiple] = false;
}
}
}
for(int[] range : ranges) {
int ans = primeCounters[range[1]] - primeCounters[range[0] - 1];
if(ans == 0)
System.out.println("NONE");
else
System.out.println(ans);
}
}
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int testcases = Integer.parseInt(reader.readLine());
int ranges[][] = new int[testcases][2];
int maxNumber = 0;
for(int t = 0; t < testcases; t++) {
String range[] = reader.readLine().split(" ");
ranges[t][0] = Integer.parseInt(range[0]);
ranges[t][1] = Integer.parseInt(range[1]);
maxNumber = Math.max(maxNumber, ranges[t][1]);
}
primeCounters(ranges, maxNumber);
}
}
#include <bits/stdc++.h>
using namespace std;
void primeCounters(vector<pair<int, int>> &ranges, int size) {
vector<bool> primeSieve(size + 1, true);
vector<int> cp(size + 1, 0);
vector<int> primeCounter(size + 1, 0);
primeSieve[0] = false;
primeSieve[1] = false;
for(int number = 2; number <= size; number++) {
if(primeSieve[number]) {
cp[number] = cp[number - 1] + 1;
} else {
cp[number] = cp[number - 1];
}
if(primeSieve[cp[number]]) {
primeCounter[number] = primeCounter[number - 1] + 1;
} else {
primeCounter[number] = primeCounter[number - 1];
}
if(primeSieve[number]) {
for(int multiple = number * number; multiple <= size; multiple += number) {
primeSieve[multiple] = false;
}
}
}
for(auto range : ranges) {
int ans = primeCounter[range.second] - primeCounter[range.first - 1];
if(ans == 0) {
cout << "NONE" << endl;
} else {
cout << ans << endl;
}
}
}
int main() {
int testcases;
cin >> testcases;
vector<pair<int, int>> ranges(testcases);
int maxNumber = 0;
for(int t = 0; t < testcases; t++) {
int l, r;
cin >> l >> r;
ranges[t] = {l, r};
maxNumber = max(maxNumber, r);
}
primeCounters(ranges, maxNumber);
return 0;
}
def prime_counters(ranges, size):
prime_sieve = [True] * (size + 1)
cp = [0] * (size + 1)
prime_counters = [0] * (size + 1)
prime_sieve[0] = False
prime_sieve[1] = False
for number in range(2, size + 1):
if prime_sieve[number] is True:
cp[number] = cp[number - 1] + 1
else:
cp[number] = cp[number - 1]
if prime_sieve[cp[number]] is True:
prime_counters[number] = prime_counters[number - 1] + 1
else:
prime_counters[number] = prime_counters[number - 1]
if prime_sieve[number] is True:
for multiple in range(number*number, size + 1, number):
prime_sieve[multiple] = False
for l, r in ranges:
ans = prime_counters[r] - prime_counters[l - 1]
if ans == 0:
print("NONE")
else:
print(ans)
if __name__ == '__main__':
testcases = int(input())
ranges = []
max_number = 0
for t in range(testcases):
l, r = tuple(map(int, input().split()))
ranges.append((l, r))
max_number = max(max_number, r)
prime_counters(ranges, max_number)