NC53079. Forsaken喜欢数论
描述
Forsaken有一个有趣的数论函数。对于任意一个数
，)
会返回的最小质因子。如果这个数没有最小质因子，那么就返回0。
现在给定任意一个
，Forsaken想知道%7D)
的值。
输入描述
一个整数
输出描述
一个整数代表上面的求和式的值。
示例1
输入:
4
输出:
7
NC53079. Forsaken喜欢数论
描述
输入描述
一个整数
输出描述
一个整数代表上面的求和式的值。
示例1
输入:
4
输出:
7
C++ 解法, 执行用时: 950ms, 内存消耗: 235204K, 提交时间: 2023-08-13 15:32:34
#include<bits/stdc++.h>
using namespace std;
long long int a[30000086]={0},i,j,n,su=0;
int main()
{
cin>>n;
for(i=2;i<=n;i++)
{
if(a[i]){su+=a[i];continue;}
for(j=i;j<=n;j+=i)
if(a[j]==0)a[j]=i; //只要是i的倍数，最小质数因子就是一样的
su+=i; //因为当前前项可能忘记加了
}
cout<<su;
}