I’m trying to implement Segmented Sieve for the problem. I can’t figure out at which testcase it might have failed. At which test case this has failed?
edit:
Problem: PRIME1 - Prime Generator
Any suggestions on:
- how to check against all test cases for a problem
- how to find at which test case the code might have failed (some tool or feature I might not have known of)
are appreciated.
// #include <bits/stdc++.h>
#include <iostream>
#include <vector>
using namespace std;
void fillPrime(vector<long long>& v, long long& limit) {
vector<int> isPrime(limit+1, 1);
for (long long i = 2; i*i <= limit; i++) {
if (isPrime[i] == 1) {
v.push_back(i);
for (long long j = 2*i; j <= limit; j += i) {
isPrime[j] = 0;
}
}
}
}
void primeRange(int& m, int& n, vector<long long>& primes) {
if(m < 2) m = 2;
if(n < m) return;
vector<int> isPrime(n-m+1, 1);
for(const long long& p : primes) {
if(p*p > n) break;
long long st = (m/p)*p;
if(st < m) st += p;
if(st == p) st += p;
for(long long j = st; j <= n; j += p) {
isPrime[j-m] = 0;
}
}
for (int i = m; i <= n; i++){
if (isPrime[i-m] == 1) {
cout << i << endl;
}
}
}
int main() {
int t;
cin >> t;
long long limit = 31622;
vector<long long> primes;
fillPrime(primes, limit);
while (t--) {
int m, n;
cin >> m >> n;
primeRange(m, n, primes);
cout << endl;
}
return 0;
}
