Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <functional>
- #include <bitset>
- #include <math.h>
- #include <time.h>
- #include <stdlib.h>
- #include <algorithm>
- #include <iostream>
- #include <string>
- #include <vector>
- #include <set>
- #include <map>
- #include <sstream>
- #include <queue>
- #include <string.h>
- #include <numeric>
- using namespace std;
- typedef vector<int> vi;
- typedef vector<vi> vvi;
- typedef pair<int,int> ii;
- typedef long long ll;
- #define sz(a) int((a).size())
- #define pb push_back
- #define all(c) (c).begin(),(c).end()
- #define tr(c,i) for(typeof((c).begin() i = (c).begin(); i != (c).end(); i++)
- #define present(c,x) ((c).find(x) != (c).end())
- #define cpresent(c,x) (find(all(c),x) != (c).end())
- vi primes;
- bool prime[1000010];
- void sieve (ll N)
- {
- memset(prime,1,sizeof prime);
- prime[0] = prime[1] = 1;
- for (ll i=2 ; i<=N ; i++)
- {
- if (!prime[i]) continue;
- for (ll j = i*i ; j<=N ; j+=i)
- {
- prime[j] = 0;
- }
- primes.pb(i);
- }
- }
- ll calc (ll N)
- {
- ll ret=0;
- for (int i=0 ; i<sz(primes) ; i++)
- {
- if (primes[i] > N) break;
- ll q = primes[i];
- while (q <= N)
- {
- ret += floor(((N-q)*1.0)/q) + 1;
- q*=primes[i];
- }
- }
- return ret;
- }
- int main ()
- {
- //freopen("*.in","r",stdin);
- //freopen("*.out","w",stdout);
- sieve(1000000);
- int N;
- while (cin >> N)
- {
- cout << calc(N) << endl;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement