Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long int ll;
- const int mx=1e6+123;
- bool is_prime[mx];
- vector<int>prime;
- void prime_gen(ll n)
- {
- is_prime[2]=1;
- for(int i=3;i<=n;i+=2)
- {
- is_prime[i]=1;
- }
- for(int i=3;i*i<=n;i+=2)
- {
- if(is_prime[i]==1)
- {
- for(int j=i*i;j<=n;j+=(i+i))
- {
- is_prime[j]=0;
- }
- }
- }
- prime.push_back(2);
- for(int i=3;i<=n;i+=2)
- {
- if(is_prime[i]==1) prime.push_back(i);
- }
- }
- bool Number_div(ll n)
- {
- ll cnt=0;
- for(auto u:prime)
- {
- if(u*u>n) break;
- if(n%u==0)
- {
- cnt++;
- while(n%u==0)
- {
- n/=u;
- }
- }
- }
- if(n>1) cnt++;
- if(cnt==2) return true;
- else return false;
- }
- int main()
- {
- prime_gen(1e6);
- ll n;
- cin>>n;
- ll ans=0;
- for(ll i=1;i<=n;i++ )
- {
- if(Number_div(i)==true) ans++;
- }
- cout<<ans;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement