求10的10次方内素数的个数与素数和的模板

Myth丶恋晨 2022-12-10 02:28 132阅读 0赞

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    ll check(ll v, ll n, ll ndr, ll nv) { 
        return v >= ndr ? (n / v - 1) : (nv - v);
    }
    ll primenum(ll n) // O(n^(3/4))
    { 
      ll r = (ll)sqrt(n);
      ll ndr = n / r;
      assert(r*r <= n && (r+1)*(r+1) > n);
      ll nv = r + ndr - 1;
      std::vector<ll> S(nv+1);
      std::vector<ll> V(nv+1);
      for(ll i=0;i<r;i++) { 
        V[i] = n / (i+1);
      }
      for(ll i=r;i<nv;i++) { 
        V[i] = V[i-1] - 1;
      }
      for(ll i = 0;i<nv;i++) { 
        S[i] = V[i] - 1; //求素数个数
      }
      for(ll p=2;p<=r;p++) { 
        if(S[nv-p] > S[nv-p+1]) { 
          ll sp = S[nv-p+1]; // sum of primes smaller than p
          ll p2 = p*p;
          for(ll i=0;i<nv;i++) { 
            if(V[i] >= p2) { 
              S[i] -= 1LL  * (S[check(V[i] / p, n, ndr, nv)] - sp); //求素数个数
            }
            else break;
          }
        }
      }
      return S[0];
    }
    ll primesum(ll n) // O(n^(3/4))
    { 
      ll r = (ll)sqrt(n);
      ll ndr = n / r;
      assert(r*r <= n && (r+1)*(r+1) > n);
      ll nv = r + ndr - 1;
      std::vector<ll> S(nv+1);
      std::vector<ll> V(nv+1);
      for(ll i=0;i<r;i++) { 
        V[i] = n / (i+1);
      }
      for(ll i=r;i<nv;i++) { 
        V[i] = V[i-1] - 1;
      }
      for(ll i = 0;i<nv;i++) { 
        S[i] = V[i] * ( V[i] + 1) / 2 - 1; //求素数和
      }
      for(ll p=2;p<=r;p++) {  // p is prime 
        if(S[nv-p] > S[nv-p+1]) { 
          ll sp = S[nv-p+1]; // sum of primes smaller than p
          ll p2 = p*p; 
          for(ll i=0;i<nv;i++) { 
            if(V[i] >= p2) { 
            S[i] -= p* (S[check(V[i] / p, n, ndr, nv)] - sp); //求素数和
            }
            else break;
          }
        }
      }
      return S[0];
    }
    int main(int argc, char const *argv[]) { 
    // std::cout << primesum(1e6) << '\n';
      std::cout << primenum(1e10) << '\n';
      std::cout << primesum(23) << '\n';
      cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
      return 0;
    }

**注：** 共三个函数：①check函数 ②primenum函数（返回素数个数）③primesum函数（返回n以内的素数和）