算法训练素因子去重

曾经终败给现在 2022-03-02 06:18 149阅读 0赞

算法训练 素因子去重

时间限制：1.0s   内存限制：256.0MB

问题描述

给定一个正整数n，求一个正整数p，满足p仅包含n的所有素因子，且每个素因子的次数不大于1

输入格式

一个整数，表示n

输出格式

输出一行，包含一个整数p。

样例输入

1000

样例输出

10

数据规模和约定

n<=10^12  
　　样例解释：n=1000=2^3\*5\*3，p=2\*5=10

**题解：题目的样例解释有问题，应该是2^3\*5^3才等于1000，所以道题根本在于求素因子，然后去重（可以用stl set容器自动去重，有序）后累乘。set用法传送门：**[https://blog.csdn.net/memory\_qianxiao/article/details/79603977][https_blog.csdn.net_memory_qianxiao_article_details_79603977]

#include<bits/stdc++.h>
    using namespace std;
    set<int>s;
    bool Isprime(long long n)
    {
        for(int i=2;i<=sqrt(n);i++)
        {
            if(n%i==0)
                return false;
        }
        return true;
    }
    int main()
    {
        long long n,ans=1;
        cin>>n;
        for(long long i=2;i<=n;i++)
        {
            if(n%i==0&&Isprime(i))
            {
                s.insert(i);
                n/=i;
            }
        }
        set<int>::iterator it;
        for(it=s.begin();it!=s.end();it++)
        {
            ans*=*it;//*it表示访问表示的实体
        }
        cout<<ans<<endl;
        return 0;
    }

[https_blog.csdn.net_memory_qianxiao_article_details_79603977]: https://blog.csdn.net/memory_qianxiao/article/details/79603977

发表评论取消回复

表情：

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

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

相关阅读

相关【算法】数组合并去重算法

文章目录删除有序数组重复项删除特定值有序数组合并链表去重合并算法删除有序数组重复项由于数组是有序的，因此只要判断当前数组元素是

Myth丶恋晨/ 2024年03月29日 15:45/ 0 赞/ 85 阅读

相关算法基础（数组去重）

请用js去掉数组中的重复值，比如把\[1,3,3,2,5,1,5,3\]变成\[1,3,2,5\]。 var arr = [1,3,3,2,5,1,5,3];

向右看齐/ 2023年08月17日 15:23/ 0 赞/ 118 阅读

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

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

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

相关有序向量去重算法

文章目录算法简述算法实现算法简述有序向量去掉重复的元素算法实现 // 有序向量的唯一算法,

约定不等于承诺〃/ 2023年06月27日 11:24/ 0 赞/ 15 阅读

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

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

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

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

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

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

相关分解素因子

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

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

相关 hdu 5108 求最大素因子

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

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

相关算法训练素因子去重

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

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

相关算法训练素因子去重

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

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