1 / 2
Sep 2021

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 Generator6
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;
}
  • created

    Sep '21
  • last reply

    Sep '21
  • 1

    reply

  • 543

    views

  • 2

    users

  • 1

    link