fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <cmath>
  4.  
  5. using namespace std;
  6.  
  7. vector<int> simpleSieve(int limit) {
  8.     vector<bool> sieve(limit + 1, true);
  9.     sieve[0] = sieve[1] = false;
  10.     vector<int> primes;
  11.  
  12.     for (int num = 2; num <= limit; num++) {
  13.         if (sieve[num]) {
  14.             primes.push_back(num);
  15.             for (int multiple = num * num; multiple <= limit; multiple += num) {
  16.                 sieve[multiple] = false;
  17.             }
  18.         }
  19.     }
  20.     return primes;
  21. }
  22.  
  23. void segmentedSieve(int m, int n) {
  24.     int limit = sqrt(n) + 1;
  25.     vector<int> primes = simpleSieve(limit);
  26.  
  27.     vector<bool> is_prime(n - m + 1, true);
  28.  
  29.     for (int prime : primes) {
  30.         int start = max(prime * prime, (m + prime - 1) / prime * prime);
  31.         for (int j = start; j <= n; j += prime) {
  32.             is_prime[j - m] = false;
  33.         }
  34.     }
  35.  
  36.     if (m == 1) {
  37.         is_prime[0] = false;
  38.     }
  39.  
  40.     for (int i = 0; i <= n - m; i++) {
  41.         if (is_prime[i]) {
  42.             cout << i + m << endl;
  43.         }
  44.     }
  45. }
  46.  
  47. int main() {
  48.     int t;
  49.     cin >> t;
  50.  
  51.     for (int test_case = 0; test_case < t; test_case++) {
  52.         int m, n;
  53.         cin >> m >> n;
  54.  
  55.         segmentedSieve(m, n);
  56.  
  57.         if (test_case < t - 1) {
  58.             cout << endl; 
  59.         }
  60.     }
  61.  
  62.     return 0;
  63. }
  64.  
Success #stdin #stdout 0s 5252KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/7NkJvC
problem PRIME1, based on SPOJ submission 33495939 (CPP), 2024-09-16 15:05:56
language:
C++ (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!