Submission #60544235

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define nl "\n";
#define inf LLONG_MAX
#define pb push_back
#define pi pair<int, int>
#define mp make_pair
#define ff first
#define ss second
#define show(x) cerr << #x << " is " << x << nl;
#define showw(x, y) cerr << #x << " is " << x << " " << #y << " is " << y << nl;
#define showall(x) cerr << #x << " is "; for (auto i : x) {cerr << i << " ";} cerr << nl;
vector<int> gen(int maxim){
  vector<bool> pos(maxim+1, true);
  pos[0] = false;
  pos[1] = false;
  for (int i=2; i<=sqrt(maxim); i++){
    if(pos[i]){
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define nl "\n";
#define inf LLONG_MAX
#define pb push_back
#define pi pair<int, int>
#define mp make_pair
#define ff first
#define ss second
#define show(x) cerr << #x << " is " << x << nl;
#define showw(x, y) cerr << #x << " is " << x << " " << #y << " is " << y << nl;
#define showall(x) cerr << #x << " is "; for (auto i : x) {cerr << i << " ";} cerr << nl;

vector<int> gen(int maxim){
	vector<bool> pos(maxim+1, true);
	pos[0] = false;
	pos[1] = false;
	for (int i=2; i<=sqrt(maxim); i++){
		if(pos[i]){
			for (int j=i*i; j<=maxim; j+= i){
				pos[j] = false;
			}
		}
	}
	vector<int> p;
	for (int i=0; i<=maxim; i++){
		if(pos[i]) p.pb(i);
	}
	return p;
}

int pow(int x){
	int prod = 1;
	for (int i=0; i<8; i++) prod *= x;
	return prod;
}

signed main(){
	fastio
	int n;
	cin >> n;
	int base = sqrt(n);
	vector<int> primes = gen(base);
	if(primes.empty()){
		cout << 0 << nl;
		return 0;
	}
	showall(primes)
	int bbase = sqrt(base);
	auto b = upper_bound(primes.begin(), primes.end(), bbase) - primes.begin() - 1;
	//show(base)
	if(b<0){
		cout << 0 << nl;
		return 0;
	}
	int cnt = 0;
	for (int i=0; i<=b; i++){
		int other = base/primes[i];
		auto lb = upper_bound(primes.begin(), primes.end(), other) - primes.begin();
		if(lb-1>i) {
			//showw(primes[i], lb)
			cnt += (lb-1-i);
		}
	}
	int num = 2;
	while(pow(num)<=n){
		if(find(primes.begin(), primes.end(), num)!=primes.end()) {
			//show(num)
			cnt++;
		}
		num++;
	}
	cout << cnt << nl;
    return 0;
}

Submission Info

Judge Result