#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define pi pair<int,int>
#define ff first
#define ss second
#define pb push_back
#define all(v) v.begin(),v.end()
#define toUpper(s) transform(s.begin(), s.end(), s.begin(), ::toupper)
#define toLower(s) transform(s.begin(), s.end(), s.begin(), ::tolower)
#define flash ios_base::sync_with_stdio(0);cin.tie(0)
#define MAX 100007
vector sieve(int l, int r) {
bool isPrime[MAX];
memset(isPrime, true, sizeof(isPrime));
for (int i = 2; i * i <= MAX; i++) {
if (isPrime) {
for (int j = i * i; j <= MAX; j += i) {
isPrime[j] = false;
}
}
}
vector<int>primes;
primes.pb(2);
for (int i = 3; i <= MAX; i += 2) {
if (isPrime[i])
primes.pb(i);
}
return primes;
}
void printPrimes(int l, int r, vector primes) {
bool isPrime[l - r + 1];
for (int i = 0; i <= r - l; i++) {
isPrime[i] = true;
}
for (int i = 0; primes[i]*primes[i] <= r; i++)
{
int currPrime = primes[i];
int base = (l / currPrime) * (currPrime);
if (base < l) {
base += currPrime;
}
for (int j = base; j <= r; j += currPrime) {
isPrime[j - l] = false;
}
if (base == currPrime) {
isPrime[base - l] = true;
}
}
if (l == 1) {
isPrime[0] = false;
}
for (int i = 0; i <= r - l; i++) {
if (isPrime[i]) {
cout << i + l << endl;
}
}
cout << endl;
}
int32_t main() {
flash;
#ifndef ONLINE_JUDGE
freopen(“input.txt”, “r”, stdin);
freopen(“output.txt”, “w”, stdout);
#endif
int t; cin >> t;
while (t--) {
int l, r;
cin >> l >> r;
vector<int> primes = sieve(l, r);
printPrimes(l, r, primes);
}
return 0;
}
created
last reply
- 1
reply
- 514
views
- 2
users