Advertisement
sajid161

Class - 28 : Task - 1

Jan 25th, 2025
109
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.07 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long int ll;
  4. const int mx=1e6+123;
  5. bool is_prime[mx];
  6. vector<int>prime;
  7. void prime_gen(ll n)
  8. {
  9.     is_prime[2]=1;
  10.     for(int i=3;i<=n;i+=2)
  11.     {
  12.         is_prime[i]=1;
  13.     }
  14.     for(int i=3;i*i<=n;i+=2)
  15.     {
  16.         if(is_prime[i]==1)
  17.         {
  18.             for(int j=i*i;j<=n;j+=(i+i))
  19.             {
  20.                 is_prime[j]=0;
  21.             }
  22.         }
  23.     }
  24.     prime.push_back(2);
  25.     for(int i=3;i<=n;i+=2)
  26.     {
  27.         if(is_prime[i]==1) prime.push_back(i);
  28.     }
  29. }
  30. bool Number_div(ll n)
  31. {
  32.    ll cnt=0;
  33.    for(auto u:prime)
  34.    {
  35.        if(u*u>n) break;
  36.  
  37.        if(n%u==0)
  38.        {
  39.            cnt++;
  40.            while(n%u==0)
  41.            {
  42.  
  43.                n/=u;
  44.  
  45.            }
  46.        }
  47.  
  48.  
  49.    }
  50.    if(n>1) cnt++;
  51.    if(cnt==2) return true;
  52.    else return false;
  53. }
  54. int main()
  55. {
  56.     prime_gen(1e6);
  57.         ll n;
  58.         cin>>n;
  59.         ll ans=0;
  60.         for(ll i=1;i<=n;i++ )
  61.         {
  62.             if(Number_div(i)==true) ans++;
  63.         }
  64.  
  65.         cout<<ans;
  66.  
  67. }
  68.  
  69.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement