找因子

因子

• 做个不严谨的定义，因子就是能被n整除的数。
• 不过题目还有一个要求，这个因子不能是1和它本身。

（1）普通做法（时间复杂度O(n)）

知道了因子定义后，就简单了，照普通做法。

1. 遍历2—n-1。
2. 如果他能被n整除，sum就加上这个因子。
3. 最后输出sum。

用代码实现：

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int sum=0,n;
    cin>>n;
    for (int i=2;i<=n-1;i++)
    {//遍历2到n-1，判断i是否能被n整除。
        if (n%i==0)
        {//如果i是n的因子，那么加入sum。
            sum=sum+i;
        }
    }
    cout<<sum;
    return 0;
}

（2）进阶做法（时间复杂度根号n）

这个方法对找因子的提升很大，假设n=100'0000'0000(一百亿)。上一个方法要循环约100'0000'0000次，但这个只要10'0000次。

• 这个方法用了这个规律：因子是成对出现的，如果i能够被n整除，那么n/i也一定能被n整除。
• 比如：24如果有因子3，那就一定有因子24/3，也就是8，24有因子6，那就一定有因子4。
• 不过需要注意的是，如果n是完全平方数，（也就是n可以拆分成i*i的形式，如：9=3 *3，16=4 *4，那么9、16就是完全平方数）那么sum加完后还要减i，因为有可能i=n/i，所以，要减去i。
• 其实，这个方法的原理很简单，就是小学学过的公式——被除数/除数=商，那么有 被除数/商=除数。

代码实现思路：

1. 遍历2到，（根号n）-1。
2. 如果i能被n整除，那么sum加i加上n/i。
3. 最后判断，如果i*i为n，那么i为完全平方数，sum-=i。
4. 输出答案。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int  sum=0,n,i=1;
    cin>>n;
    for (i=2;i*i<n;i++)
    //实现遍历2到根号n。
    //根号n可以用i*i<n实现。(第一步)。
    {
        if (n%i==0)
        {
//如果i是n的因数,那sum+i+n/i(第二步)。
            sum=sum+i+n/i;
        }
    }
    if (i*i==n)
    {//循环完之后i已经是最接近根号的了。
        sum+=i;
        //因为前面是i*i<n不是i*i<=n,
        //所以这里不用减,加i即可。
    }
    cout<<sum;//输出答案
    return 0;
}

这也不难啊

#include <bits/stdc++.h>
using namespace std;
int n,ans;
int main()
{
    cin>>n;
    for(int i=2;i<n;i++)
    {
        if(n%i==0)
            ans+=i;
    }
    cout<<ans;
    return 0;
}

#include<bits/stdc++.h> 
using namespace std;
int fun(int n)
{
	int r=0;
	for(int i=2;i<=sqrt(n);i++) 
	{
		if(n%i==0)
		{
			if(i==sqrt(n))
			{
				r+=i;
			}
			else
			{
				r=r+i+(n/i);
			}
		} 
	}
	return r; 
}
int main()
{
	int n;
	cin>>n;
	cout<<fun(n);
	return 0; 
}

唯一分解定理

#include <bits/stdc++.h>
using namespace std;
int n,y;
map<int,int>m;
int ans=1,s,t;
int main(){
	cin>>n;
	y=n;
	for (int i=2;i<=sqrt(n);i++){
		while (n%i==0){
			m[i]++;
			n/=i;
		}
	}
	if (n>1)m[n]++;
	for (const auto&it:m){
		s=0;t=1;
		for (int i=0;i<=it.second;i++){
			s+=t;
			t*=it.first;
		}
		ans*=s;
	}
	cout<<ans-1-y;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n, ans = 0;
    cin >> n;
    for (int i = 2; i < n; i++)
        if (n % i == 0)
            ans += i;
    cout << ans << endl;
    return 0;
}

错误率真高【doge】

#include <bits/stdc++.h>
using namespace std;
int main()
{
	int n, x = 0;
	cin >> n;
	for (int i = 2; i <= sqrt(n); i++) //循环n的因子范围2~sqrt(n),成对求解n的因子
    {
		if (n % i == 0) //如果i是n的因子
        {
			
			if (i != n / i) //判断两个因子是否相等
				x += i + n / i;
            else
				x += i;
		}
	}
	cout << x;
    return 0;
}