算法训练-素因子去重--素数筛！！！

た入场券 2023-01-10 03:55 122阅读 0赞

资源限制  
时间限制：1.0s 内存限制：256.0MB  
问题描述  
　　给定一个正整数n，求一个正整数p，满足p仅包含n的所有素因子，且每个素因子的次数不大于1  
输入格式  
　　一个整数，表示n  
输出格式  
　　输出一行，包含一个整数p。  
样例输入  
1000  
样例输出  
10  
数据规模和约定  
　　n<=10^12  
　　样例解释：n=1000=23\*5\*3，p=2\*5=10\*\*（应该是n=1000=23\*5^3）\*\*  
　　  
**思路**  
题目输入n,找n的因子，让因子去重，重复因子只乘一次，输出它。  
思路一：输入数n,for循环从2到n，找到因子，因子乘一次。  
思路二：可以根号n的复杂度去模拟，其实隐含了一个素数筛，最后乘以操作后的n  
**思路一**

#include<bits/stdc++.h>
    using namespace std;
    int main(){
        
    	long long int n,p=1,i;
    	scanf("%lld",&n);
    	for(i=2;i<=n;i++){
        
    
    		if(n%i==0){
        
    			p*=i;
    			while(n%i==0){
        
    			n/=i;
    		}
    		}
    	}
    	printf("%lld",p);
    return 0;
    }

**思路二**

#include<iostream>
    using namespace std;
    int main()
    {
        
        long long n;
        cin>>n;
        long long p=1;
        for(int i=2;i*i<=n;i++)
        {
        
            if(n%i==0)
            {
        
                p*=i;
                while(n%i==0)
                {
        
                    n/=i;
                }
            }
        }
        if(n>1)
        {
        
            p*=n;
        }
        cout<<p<<endl;
        return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关【数论算法】素数筛

目录 1.概述 2.代码实现 2.1.试除法 2.2.埃拉托斯特尼筛法 2.3.欧拉筛法 1.概述（1）在了

￡神魔★判官ぃ/ 2023年10月07日 22:54/ 0 赞/ 26 阅读

相关素数筛

目录题目思路1 思路2 思路3 题目给定一个正整数n(2≤n≤10000)，先输出2~n之间的素数个数

拼搏现实的明天。/ 2023年10月06日 16:35/ 0 赞/ 79 阅读

相关基础算法题——素因子去重

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

梦里梦外;/ 2023年07月15日 09:20/ 0 赞/ 19 阅读

相关算法训练-素因子去重--素数筛！！！

资源限制时间限制：1.0s 内存限制：256.0MB 问题描述　　给定一个正整数n，求一个正整数p，满足p仅包含n的所有素因子，且每个素因子的次数不大于1

た入场券/ 2023年01月10日 03:55/ 0 赞/ 123 阅读

相关 Java 蓝桥杯算法训练 ALGO_190_素因子去重

Java 蓝桥杯算法训练 ALGO\_190\_素因子去重问题描述给定一个正整数n，求一个正整数p，满足p仅包含n的所有素因子，且每个素因子的次数不大于1

水深无声/ 2022年12月14日 12:25/ 0 赞/ 144 阅读

相关【算法与数据结构】——素数筛

素数筛是比较常用的基础知识，通常穿插在题目中，作为题解的一部分。作简单记录，给自己看。埃氏筛埃拉托斯特尼筛法，简称埃氏筛。学习埃氏筛之前，我们先看一下暴力

我会带着你远行/ 2022年10月16日 08:45/ 0 赞/ 140 阅读

相关分解素因子

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

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

相关 Pairs Forming LCM 素数筛和素因子分解

Pairs Forming LCM ：[http://acm.hust.edu.cn/vjudge/contest/view.action?cid=109329\problem

本是古典何须时尚/ 2022年07月29日 08:50/ 0 赞/ 191 阅读

相关算法训练素因子去重

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

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

相关算法训练素因子去重

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

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