hdu 5108 求最大素因子

桃扇骨 2022-08-04 00:35 147阅读 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=32000;
    
    bool vis[N];
    int prime[10000];
    
    int main()
    {
        int p=1;
        prime[0]=2;
        for(int i=3;i<N;i+=2)
        {
            if(!vis[i])
            {
                prime[p++]=i;
                for(int j=i+i;j<N;j+=i)这里老写错
                {
                    vis[j]=1;
                }
            }
        }
        int n;
        while(~scanf("%d",&n))
        {
            int tmp=n;
            if(n==1)特判啊
            {
                puts("0");
                continue;
            }
            int t=n;
    
            for(int i=0;prime[i]*prime[i]<=n;i++)
            {
                while(n%prime[i]==0) n/=prime[i],t=prime[i];
            }
            t=max(t,n);     //较大的那个
            printf("%d\n",tmp/t);
        }
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，147人围观）

还没有评论，来说两句吧...

相关阅读

相关 1071. 字符串的最大公因子

题目： [1071. 字符串的最大公因子][1071.] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow

小咪咪/ 2023年07月13日 13:37/ 0 赞/ 122 阅读

相关（C++）求最大公因子（辗转相除法）

具体算法也可以看这篇： [https://zhuanlan.zhihu.com/p/151447583][https_zhuanlan.zhihu.com_p_1514475

Bertha 。/ 2023年02月26日 06:19/ 0 赞/ 7 阅读

相关分解素因子

分解素因子 Time Limit: 1500ms Memory limit: 10000K 有疑问？点这里^\_^ 题目描述假设x是一个正整数，它的值不超过

￡神魔★判官ぃ/ 2022年08月10日 05:52/ 0 赞/ 192 阅读

相关 hdu 5108 求最大素因子

include<bitset> include<map> include<vector> include<cstdio> in

桃扇骨/ 2022年08月04日 00:35/ 0 赞/ 148 阅读

相关 hdu 2136 最大素因数的位置

求最大素因数在素数中排老几。预处理出素数就行，然后在筛选素数的过程中，把每个数对应的素因数记录下来，最后每个数的素因数肯定都是最大的，因为不断有更大的素因数取代这个位置

àì夳堔傛蜴生んèń/ 2022年08月03日 15:58/ 0 赞/ 150 阅读

相关 HDU 2841 Visible Trees （容斥原理+素因子分解）

HDU 2841 Visible Trees （容斥原理+素因子分解）：[http://acm.hdu.edu.cn/showproblem.php?pid=2841][htt

﹏ヽ暗。殇╰゛Y/ 2022年07月26日 00:08/ 0 赞/ 134 阅读

相关 hdu 1695 GCD (欧拉函数+容斥原理+素因子分解)

hdu 1695 GCD (欧拉函数+容斥原理+素因子分解) ：[http://acm.hdu.edu.cn/showproblem.php?pid=1695][http_ac

绝地灬酷狼/ 2022年07月25日 15:58/ 0 赞/ 163 阅读

相关求最长素子串的长度

本来在leetcode里面搜的是哈系表相关算法练习,把这个题做完后,感觉没用到相关知识\[哭笑一波 ?\] > 给定一个字符串，请你找出其中不含有重复字符的最长子串的

﹏ヽ暗。殇╰゛Y/ 2022年03月22日 07:29/ 0 赞/ 189 阅读

相关算法训练素因子去重

问题描述　　给定一个正整数n，求一个正整数p，满足p仅包含n的所有素因子，且每个素因子的次数不大于1 输入格式　　一个整数，表示n 输出格式　　输出一行，包含一

桃扇骨/ 2022年03月16日 02:20/ 0 赞/ 143 阅读

相关算法训练素因子去重

算法训练素因子去重时间限制：1.0s 内存限制：256.0MB 问题描述　　给定一个正整数n，求一个正整数p，满足p仅包含n的所有素因子，且

曾经终败给现在/ 2022年03月02日 06:18/ 0 赞/ 138 阅读