PROBLEM LINK:
DIFFICULTY:
Simple
PREREQUISITES:
Sieve of Eratosthenes, Prefix Sums
PROBLEM:
Mangilaal wants to meet his close relatives, there are N colonies from 1 to N with each having house numbers in a particular range [li,ri] ( both inclusive).
Mangilaal wants to visit the houses which falls in the range [L,R] ( both inclusive) and decided that he will only visit the house numbers which are prime as he is fond of prime numbers.
You have to print the colony number which has the maximum number of houses visited by Mangilaal. If there are no colonies he can visit, print −1. If he can visit multiple colonies, print the lowest colony number.
QUICK EXPLANATION:
Precalculate primes and precompute the number of primes ending at every i, i < 5 * 10^4. For each of the input intervals, find the intersaction with the global interval and calculate number of primes in it using prefix sums.
EXPLANATION:
Firstly, let’s precompute an array which will tell us whether a number is prime for every number from 1 to 5 * 10^4. This can be easily done using a simple Sieve of Eratosthenes in O(N log N) complexity. Call this array prime and let prime[i] be 1, if i is prime and 0 otherwise.
For every i from 1 to 5 * 10^4 we can precompute the number of primes that occur in interval [1, i]. This can be done using the following formula for every i:
prefix[i] = prefix[i - 1] + prime[i]
Now all that’s left to do is compute the number of primes Mangilaal will visit if he chooses to go to the interval i.
We can easily derive that the left bound of i_{th} interval as: max(L_i, L), and the right bound in a similar manner as min(R_i, R), where L and R are the global bounds.
Now for each interval [i, j] we can compute the number of primes in it as prefix[j] - prefix[i - 1].
All that’s left is cancelling out the cases where left bound is greater than the right bound, and covering the base case where we haven’t found a single prime in any of the intervals.
SOLUTIONS:
Alternate Editorialist's Solution:
#include <bits/stdc++.h>
using namespace std;
int L, R;
int n;
int l[15];
int r[15];
bool prime[50005];
int pref[50005];
void sieve() {
for (int i = 2; i * i <= 50000; i++) {
if (!prime[i]) continue;
for (int j = i * i; j <= 50000; j += i) {
prime[j] = 0;
}
}
}
int main() {
memset(prime, 1, sizeof prime);
cin >> L >> R;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> l[i] >> r[i];
}
sieve();
for (int i = 2; i <= 50000; i++) {
pref[i] = pref[i - 1] + prime[i];
}
int ans = -1, cur = -1;
for (int i = 0; i < n; i++) {
int ll = max(l[i], L);
int rr = min(R, r[i]);
int tmp = max(0, pref[rr] - pref[ll - 1]);
if (tmp) {
if (ans == -1) {
ans = i + 1;
cur = tmp;
}
else if (tmp > cur) {
ans = i + 1;
cur = tmp;
}
}
}
cout << ans << '\n';
return 0;
}