算法训练素因子去重

曾经终败给现在 2022-03-02 06:18 117阅读 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 条评论，117人围观）

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

相关阅读

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

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

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

相关【Java算法】链表合并去重算法

文章目录删除有序列表中的重复元素有序链表合并删除有序列表中的重复元素既然我们要删除一个有序的链表中的重复元素，那么我们可以这样子想。如果

清疚/ 2024年03月27日 08:46/ 0 赞/ 43 阅读

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

请用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 赞/ 70 阅读

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

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

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

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

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

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

相关分解素因子

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

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

相关 hdu 5108 求最大素因子

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

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

相关 LightOJ - 1141 Number Transformation ——————BFS+素因子分解

\\Number Transformation \\ In this problem, you are given an integer number s. You can

冷不防/ 2022年05月12日 03:14/ 0 赞/ 113 阅读

相关算法训练素因子去重

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

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

相关算法训练素因子去重

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

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