数论：求一个数的因子专题（因子数，因子和，质因子）
发布时间
阅读量：
阅读量
问题1-求n的因子数、因子和
输入一个正整数N，求出这个数字存在多少个因子，以及因子之和。
分析
既需要统计因子的数量又要计算因子的总和，则希望从i=1循环到sqrt(n)的整数部分进行遍历。每当发现有i满足n%i==0时，则因数个数增加2（即分别考虑i和n/i这两个因数），对应的因数和为i加上n/i的值。需要注意的是，在处理平方根情况时（即当i等于sqrt(n)时），应避免重复计算。
代码
int cnt=0,long long sum=0; //cnt为因子数 sum为因子和 因子和可能很大，开long long
void fun(int n)
{
if(n==1) cnt=1,sum=1;
else
{
for(int i=1;i<=sqrt(n);i++) //从1遍历到根号n
{
if(n%i==0) //i能够被n整除，i为因子
{
if(i==sqrt(n)&&n/i==i) //n能够被开方，根号n和i相等的情况
{
cnt++; //因子数加一
sum+=i;
}
else
{
cnt+=2; //因子数加2 i和n/i
sum+=i+n/i;
}
}
}
}
}问题2 输出n的质因子
#include<iostream>
using namespace std;
typedef long long ll;
int main(){
ll n;
cin >> n;
for(ll i = 2; i * i <= n; i++){
while(n % i == 0) {
cout << i;
n /= i;
if(n != 1)
cout <<'*';
}
}
if(n != 1)
cout << n << endl;
}例子完全平方数（蓝桥杯）
题目
称该整数值a为完全平方值。当且仅当它可表示为某一特定值的平方时才被称为完全平方式。具体而言，则存在一对应于该数值b（其中b也是一个特定值），满足关系式a = b²。
给定一个正整數 n，請希望找出最小的正整數 x，使其與 n 的 乘積 成為一個 完全 平方數。
代码
#include<iostream>
using namespace std;
typedef long long ll;
int main(){
ll n;
cin >> n;
for(ll i = 2; i * i <= n; i++){
while(n % i == 0) {
cout << i;
n /= i;
if(n != 1)
cout <<'*';
}
}
if(n != 1)
cout << n << endl;
}全部评论 (0)
还没有任何评论哟~