from collections import defaultdict, deque, Counter
from functools import lru_cache, reduce
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
from random import randint
from math import *
import operator
import sys
from itertools import accumulate
hpop = heappop
hpush = heappush
MOD = 10**9 + 7
input=sys.stdin.readline
def solution():
n = int(input())
arr = list(map(int, input().split()))
m = int(input())
max_num = max(arr)
sm_factor = [0]*(max_num + 1)
for i in range(2, max_num + 1):
if sm_factor[i] == 0:
for j in range(i, max_num + 1, i):
if sm_factor[j] == 0 :
sm_factor[j] = i
prime_freq = [0]*(max_num + 1)
for val in arr:
t = sm_factor[val]
while t:
while val % t == 0:
val //= t
prime_freq[t] += 1
t = sm_factor[val]
for i in range(1, len(prime_freq)):
prime_freq[i] += prime_freq[i-1]
for _ in range(m):
l,r = map(int, input().split())
if l >= len(prime_freq):
print(0)
else:
if r >= len(prime_freq): r = -1
print(prime_freq[r] - prime_freq[l-1])
def main():
t = 1
for _ in range(t):
solution()
main()
//بِسْمِ اللَّهِ الرَّحْمَنِ الرَّحِيمِ
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
template<typename T> using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define Samo7a ios_base::sync_with_stdio(false);cin.tie(nullptr); cout.tie(nullptr);
#define re return
#define FX(n) fixed << setprecision(n)
#define endl '\n'
#define sz(v) (int) v.size()
#define all(v) v.begin(),v.end()
#define allr(v) v.rbegin(),v.rend()
#define pb push_back
#define eb emplace_back
#define pi acos(-1)
#define F first
#define S second
const int N = 1e7 + 10, MOD = 1e9 + 7;
const int dx[]{1, -1, 0, 0, 1, -1, 1, -1};
const int dy[]{0, 0, 1, -1, 1, -1, -1, 1};
inline void debugMode() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
#endif // ONLINE_JUDGE
}
//الشَّيْطَانُ يَعِدُكُمُ الْفَقْرَ وَيَأْمُرُكُم بِالْفَحْشَاءِ ۖ وَاللَّهُ يَعِدُكُم مَّغْفِرَةً مِّنْهُ وَفَضْلًا ۗ وَاللَّهُ وَاسِعٌ عَلِيمٌ (268)
//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//
ll divi[1LL * N];
int f[1LL * N];
void seive() {
bitset<N> is_prime;
is_prime.set();
is_prime[0] = 0, is_prime[1] = 0;
for (int i = 2; i<= 1e7; i++) {
if (not is_prime[i])
continue;
for (int j = i; j <= 1e7; j += i) {
if (i != j)
is_prime[j] = 0;
divi[i] += f[j];
}
}
}
void TestCase() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
f[x]++;
}
seive();
for (int i = 1; i < N; i++)
divi[i] += divi[i - 1];
int m;
cin >> m;
while (m--) {
int l, r;
cin >> l >> r;
l = min((int) 1e7, l), r = min((int) 1e7, r);
cout << divi[r] - divi[l - 1] << endl;
}
}
int main() {
Samo7a
debugMode();
int t = 1;
//cin >> t;
while (t--) {
TestCase();
}
re 0;
}Teddy and Tweety | Partitioning binary strings |
Special sets | Smallest chosen word |
Going to office | Color the boxes |
Missing numbers | Maximum sum |
13 Reasons Why | Friend's Relationship |
Health of a person | Divisibility |
A. Movement | Numbers in a matrix |
Sequences | Split houses |
Divisible | Three primes |
Coprimes | Cost of balloons |
One String No Trouble | Help Jarvis! |
Lift queries | Goki and his breakup |
Ali and Helping innocent people | Book of Potion making |
Duration | Birthday Party |
e-maze-in | Bricks Game |