SHARE
TWEET

Untitled

murs06 Dec 3rd, 2019 73 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define size 100000
  5.  
  6. int primes[size];
  7. int countv;
  8.  
  9. void sieveSimple(int n){
  10.     countv = 0;
  11.     if(n >= 2)
  12.     {
  13.         bool mark[n + 1];
  14.         for (int i = 3; i*i <= n; i+=2)
  15.         {
  16.             if (mark[i] == false)
  17.             {
  18.                 for (int j = i*i; j <= n; j+= i + i)
  19.                 {
  20.                     mark[j] = true;
  21.                 }
  22.             }
  23.         }
  24.         for (int i = 2; i <= n; ++i)
  25.         {
  26.             if (i == 2)
  27.                 primes[countv++] = i;
  28.             else if (i%2 != 0 && mark[i] == false)
  29.                 primes[countv++] = i;
  30.         }
  31.     }
  32. }
  33.  
  34. int main()
  35. {
  36.     int t;
  37.     scanf("%d", &t);
  38.  
  39.     while (t--)
  40.     {
  41.         bool marked[size + 1];
  42.         int m, n;
  43.         scanf("%d %d", &m, &n);
  44.         sieveSimple(sqrt(n));
  45.  
  46.         for (int i = 0; i < countv; ++i)
  47.         {
  48.             int a = primes[i];
  49.             int b = m/a;
  50.             b *= a;
  51.  
  52.             for (int j = b; j <= n; j+=a)
  53.             {
  54.                 if (j < m)
  55.                     continue;
  56.                 marked[j - m] = true;
  57.             }
  58.         }
  59.         for (int i = 0; i < countv; ++i)
  60.         {
  61.             if (primes[i] >= m && primes[i] <= n)
  62.                 printf("%d\n", primes[i]);
  63.         }
  64.         for (int i = 0; i < n - m + 1; ++i)
  65.         {
  66.             if (marked[i] == false && (i + m) != 1)
  67.                 printf("%d\n", i + m);
  68.         }
  69.         if (t != 0) printf("\n");
  70.     }
  71.     return 0;
  72. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top