Advertisement
MSzopa

PWD 27.01.2022 C++ Sito Eratostenesa

Jan 28th, 2022
607
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <numeric>
  4. #include <cmath>
  5.  
  6. std::vector<int> GetPrime(unsigned int n) {
  7.     std::vector<int> ret(n - 2 + 1);
  8.     std::iota(std::begin(ret), std::end(ret), 2);
  9.     int sqr = sqrt(n);
  10.     for (int i = 0; i <= sqr; i++) {
  11.         int a = 2;
  12.         while (ret[i] * a <= n) {
  13.             ret.erase(std::remove(ret.begin(), ret.end(), ret[i] * a), ret.end());
  14.             a++;
  15.         }
  16.     }
  17.     return ret;
  18. }
  19. std::vector<int> GetPrime2(unsigned int n) {
  20.     std::vector<int> ret;
  21.     std::vector<bool> prime(n+1);
  22.     int sqr = sqrt(n);
  23.     for (int i = 2; i <=n; i++) {
  24.         if (!prime[i]) {
  25.             ret.push_back(i);
  26.             if (i <= sqr) {
  27.                 int a = 2;
  28.                 while (i * a <= n) {
  29.                     prime[i * a] = true;
  30.                     a++;
  31.                 }
  32.             }
  33.         }
  34.     }
  35.     return ret;
  36. }
  37. int main()
  38. {
  39.     std::vector<int> a = GetPrime(100);
  40.     std::vector<int> b = GetPrime2(100);
  41.     for (int i = 0; i < b.size(); i++) {
  42.         std::cout << a[i]<<" "<<b[i] << std::endl;
  43.     }
  44. }
  45.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement