// 这是典型的筛式，s[i]储存的是质数想乘的个数，找到一个质数，就用
// 数组储存起来，然后更新所有质数乘以i后的数，这个状态转移s[x*i]=s[i]+1
// 是最关键的最难想到的
#include<iostream>
#include<vector>
using namespace std;
const int L = 2333333, R = 23333333;
int s[R+10],ans;
vector<int> p;
int main(){
    // 遍历所有小于等于R的数
    for(int i=2;i<=R;i++){
        if(!s[i]){
            // 这是一个质数
            s[i]=1;
            p.push_back(i);//把这个质数存进去
        }
        // 判断是否满足条件
        if(i>=L&&s[i]==12){
            ans++;
        }
        for(auto x:p){
            if(x*i>R){
                break;
            }
            else{
                s[x*i]=s[i]+1;
            }
        }
    }
    cout<<ans<<endl;
    return 0;

}

// 启发我们做比值时候结果储存要用double 被除数要用double 除数要用int
#include <iostream>;
using namespace std;
int gcd(int a,int b){
  return b?gcd(b,a%b):a;
}
int main()
{
    double a;
    int  b;
    int c, m, n = 0;
    double min = 100;
    cin >> a >> b >> c;
    double d;
    d = a / b;
    for (double i = 1;i <= c;i++)
    {
        for (int j = 1;j <= c;j++)
        {

            if(gcd((int)i,j)==1){
              double f;
              f = i  / j;
              if (f >= d && ((f - d) <= min))
              {
                m = i;
                n = j;
                min = f - d;
              }

            }


        }
    }

    cout << m << " " << n;
    // 请在此输入您的代码  1498 902 10
    return 0;
}

// 有用的知识：n个数如果最大公因数为1的话，那么无限个物品不能组成的体积是
// 无限多个的，而为1的，不能组成的体积种类是有限的，用硬币dp可以找到
#include<iostream>
using namespace std;
int gcd(int a,int b){
    return b?gcd(b,a%b):a;
}
const int N=3e5;
int dp[N];
int v[600];
int n;
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>v[i];
    }
    int g=gcd(v[0],v[1]);
    for(int i=2;i<n;i++){
        g=gcd(g,v[i]);
    }
    if(g!=1){
        cout<<0;
        return 0;
    }
    else{
        dp[0]=1;
        int m=0;
        for(int i=1;i<N;i++){
            for(int j=0;j<n;j++){
                if(i>=v[j]){
                    if(dp[i-v[j]]){
                        dp[i]=1;
                    }
                }
            }
            if(dp[i]){

            }
            else{
                m=i;
            }
        }
        cout<<m;
    }
    return 0;
}

//  这个用筛式方法即可
// 明白f[i]要么是质数，要么就是被之前的质数更新过
// 如果是质数的话，那么更新为f[i]=i就好，然后用这个质数去更新其他没有
// 被更新的数，经常用到判断if(f[i])来判断是否被更新过
#include<iostream>
using namespace std;
const int N=3e6+10;
int f[N+3];
long long s[N+3];//数值储存较大用long long
int main(){
    int n;
    cin>>n;
    for(int i=2;i<=N;i++){
        if(f[i]){
            continue;
        }
        else{
            f[i]=i;
            for(int j=2;j*i<=N;j++){
                if(f[i*j]){
                    continue;
                }
                else{
                    f[i*j]=i;
                }
            }
        }
    }
    for(int i=2;i<=N;i++){
        s[i]=s[i-1]+f[i];
    }
    while(n--){
        int k;
        scanf("%d",&k);
        printf("%lld\n",s[k]);
    }
    return 0;
}

#include<iostream>
#include<iomanip>
#include<cmath>
using namespace std;
int main(){
    double n;
    cin>>n;
    // 直接调用函数cbrt是求立方根的
    double s=cbrt(n);
    cout<<fixed<<setprecision(6)<<s;
    return 0;
}

// 国赛打卡
//二分的经典例题，以后记忆模板就用这个，当我们想要求左边界的时候，就要想办法去压缩又边
//此时是l+r>>1 是<= 当要求的是又边界时候，压缩左边 是l+r+1>>1 是<= 无论哪个，最后l才是答案
//l 与r的初始值就是数组的左右下标
#include<iostream>
using namespace std;
const int N=1e5+10;
int a[N];
int main(){
    int n,q,k;
    cin>>n>>q;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    while(q--){
        cin>>k;
        int l=0,r=n-1;
        while(l<r){
            int mid=l+r>>1;
            if(a[mid]>=k){
                r=mid;
            }
            else{
                l=mid+1;
            }
        }
        if(a[l]!=k){
            cout<<"-1 -1"<<endl;
        }
        else{
            cout<<l<<" ";
            l=0,r=n-1;
            while(l<r){
              int mid=l+r+1>>1;
              if(a[mid]<=k){
                l=mid;
              }
              else{
                r=mid-1;
              }
            }
            cout<<l<<endl;
        }
    }
    return 0;
}

//思路是用二进制来表示状态，1表示走过的，0表示没有走过
//用二维数组进行dp dp[i][j]表示在i状态下，最后到达的教学楼为j时的方案数
//进行检测：第一，是否i状态中含有j，第二，如果含有j的情况下，便利所有与j相连的点，并且这个点出现在i状态中
//转移方程为dp[i][j]+=dp[i-(1<<j)][k] 表示经过k到达的j
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=1e4;
int h[N],e[N],ne[N],idx;
int p[22][22];
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int gcd(int a,int b){
    return b?gcd(b,a%b):b;
}
int dp[1<<22][22];

int main(){
    for(int i=1;i<=21;i++){
        for(int j=i+1;j<=21;j++){
            if(gcd(i,j)==1){
                p[i-1][j-1]=1;
                p[j-1][i-1]=1;
            }
        }
    }
    dp[1][0]=1;
    int n=1<<21;
    for(int i=1;i<n;i++){
        for(int j=0;j<21;j++){
            if((i>>j&1)==0){
                continue;
            }
            else{
                for(int k=0;k<21;k++){
                    if(p[k][j]&&(i>>k&1)){
                        dp[i][j]+=dp[i-(1<<k)][k];
                    }
                }
            }
        }
    }
    ll res=0;
    for(int i=0;i<21;i++){
        res+=dp[n-1][i];
    }
    cout<<res;
    return 0;
}

//dp问题，如果不用这个砝码，就可以做到，那么有了这个砝码还可以做到j+w[i],j-w[i],w[i]-1的实现，取决于放在哪边
//类似于背包问题
#include<iostream>
using namespace std;
const int N=1e5+10;
int n;
int w[110];
bool f[110][N];
int sum;
int main(){
    cin>>n;
    sum=0;
    for(int i=1;i<=n;i++){
        cin>>w[i];
        sum+=w[i];
    }
    f[0][0]=true;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=sum;j++){
            if(f[i-1][j]){
                f[i][j]=true;
                f[i][j+w[i]]=true;
                if(j>=w[i]){
                    f[i][j-w[i]]=true;
                }
                else{
                    f[i][w[i]-j]=true;
                }
            }
        }
    }
    int res=0;
    for(int i=1;i<=sum;i++){
        if(f[n][i]){
            res++;
        }
    }
    cout<<res;
    return 0;

}

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e6+10,M=1e5+10;
char s[N],p[M];
int n,m;
int ne[M];
int main(){
    // 下标从1开始
    cin>>m>>p+1>>n>>s+1;
    // 求next数组
    for(int i=2,j=0;i<=m;i++){
        while(j&&p[i]!=p[j+1]){
            j=ne[j];
        }
        if(p[i]==p[j+1]){
            j++;
        }
        ne[i]=j;
    }
    // 匹配操作
    for(int i=1,j=0;i<=n;i++){
        while(j&&s[i]!=p[j+1]){
            j=ne[j];
        }
        if(s[i]==p[j+1]){
            j++;
        }
        if(j==m){
            cout<<i-m<<" ";//下标从1开始就是i-m+1了
            j=ne[j];//继续匹配
        }
    }
    return 0;
}

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e6+10,M=1e5+10;
char s[N],p[M];
int n,m;
int ne[M];
int main(){
    // 下标从1开始
    cin>>m>>p+1>>n>>s+1;
    // 求next数组
    for(int i=2,j=0;i<=m;i++){
        while(j&&p[i]!=p[j+1]){
            j=ne[j];
        }
        if(p[i]==p[j+1]){
            j++;
        }
        ne[i]=j;
    }
    // 匹配操作
    for(int i=1,j=0;i<=n;i++){
        while(j&&s[i]!=p[j+1]){
            j=ne[j];
        }
        if(s[i]==p[j+1]){
            j++;
        }
        if(j==m){
            cout<<i-m<<" ";//下标从1开始就是i-m+1了
            j=ne[j];//继续匹配
        }
    }
    return 0;
}