ulvis.paste.net

Paste Search Dynamic
Recent pastes
primeSieve
  1. #include <iostream>
  2. #include <bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6.  
  7.  
  8. int primeSieve(int n,int state)
  9. {
  10.         int PLT{};
  11.         bool prime[n+1];
  12.     memset(prime, true, sizeof(prime));
  13.  
  14.     for (int p=2; p*p<=n; p++)
  15.     {
  16.        if (prime[p] == true)
  17.        {
  18.            for (int i=p*2; i<=n; i += p)
  19.                prime[i] = false;
  20.        }
  21.     }
  22.  
  23.     for (int p=2; p<=n; p++)
  24.       if (prime[p])
  25.             {
  26.                 if(state == 1)
  27.                 {
  28.                     PLT++;
  29.                 }
  30.                 else
  31.                 {
  32.                     if(p == n)
  33.                         return 1;
  34.                 }
  35.             }
  36.             if(state == 1)
  37.                     return PLT;
  38.             else
  39.                     return 0;
  40.  
  41. }
  42.  
  43.  
  44. int main()
  45. {
  46.     int n, q, p;
  47.     cin >> n >> q;
  48.         int state = 1;
  49.         cout << endl << primeSieve(n,state) << endl;
  50.         state = 0;
  51.     while(q != 0)
  52.     {
  53.             cin >> p;
  54.                 cout << primeSieve(p,state) << endl;
  55.         q--;
  56.     }
  57.  
  58.     return 0;
  59. }
Parsed in 0.015 seconds