1 / 2
Jul 2020

#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

    Jul '20
  • last reply

    Jul '20
  • 1

    reply

  • 514

    views

  • 2

    users

Where’s the index?

r is greater than l, so how big is this array?

(Please edit your post and put three back ticks ``` on a line by themselves before and after the code. This will prevent the code from being mangled.)