hdu 2136 最大素因数的位置

àì夳堔傛蜴生んèń 2022-08-03 15:58 160阅读 0赞

求最大素因数在素数中排老几。

预处理出素数就行，然后在筛选素数的过程中，把每个数对应的素因数记录下来，最后

每个数的素因数肯定都是最大的，因为不断有更大的素因数取代这个位置，

输出的时候用二分搜索查找位置就行了。

#include<bitset>
    #include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;
        char c;
        while((c=getchar())<'0' || c>'9');
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res;
    }
    
    const int N=1000002;
    bitset<N> vis;
    
    int prime[150000];
    int a[N];    //存每个数最大的素因数
    
    int main()
    {
        int p=0;
    
        for(int i=2;i<N;i++)
        {
            if(!vis[i])
            {
                prime[p++]=i;
                for(int j=i;j<N;j+=i)
                {
                    vis[j]=1;
                    a[j]=i;
                }
            }
        }
        int n;
        while(~scanf("%d",&n))
        {
            if(n==1)
            {
                puts("0");
                continue;
            }
            printf("%d\n",lower_bound(prime,prime+p,a[n])-prime+1);
        }
        return 0;
    }

在贴一种更巧妙的，直接记录位置的，cnt奇数变量就是位置啊。

#include<bitset>
    #include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;
        char c;
        while((c=getchar())<'0' || c>'9');
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res;
    }
    
    const int N=1000002;
    
    int ans[N];
    
    int main()
    {
        int cnt=1;
        for(int i=2;i<N;i++)
        {
            if(ans[i])continue;    //i不是素数
            for(int j=i;j<N;j+=i)
            {
                ans[j]=cnt;         //ans[j]等于当前这个素数的位置
            }
            cnt++;
        }
        int n;
        while(~scanf("%d",&n))
        {
            printf("%d\n",ans[n]);
        }
        return 0;
    }