链接:https://ac.nowcoder.com/acm/contest/1221/A
来源:牛客网

时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 524288K,其他语言1048576K
64bit IO Format: %lld

题目描述

        Forsaken有一个有趣的数论函数。对于任意一个数xxx,f(x)f(x)f(x)会返回xxx的最小质因子。如果这个数没有最小质因子,那么就返回0。
        现在给定任意一个nnn,Forsaken想知道∑i=1nf(i)\sum_{i = 1}^{n}{f(i)}∑i=1n​f(i)的值。
        

输入描述:

一个整数nnn。

输出描述:

一个整数代表上面的求和式的值。
示例1

输入

复制

4

输出

复制

7

备注:

1≤n≤3e71 \leq n \leq 3e71≤n≤3e7

思路:线性筛法可以求1到n每个数字的最小质因子
具体思路见注释
#include <iostream>
#include<bitset>
#include<algorithm>
#include<string>
#include<cmath>
using namespace std;
const int maxn= 3e7;
const int maxn1=1e6;
int primes[maxn], cnt;
bool st[maxn];
long long ans=;
void get_primes(int n)
{
for (int i = ; i <= n; i ++ )
{
if (!st[i]) primes[cnt ++ ] = i,ans+=i;//如果一个数本身是质数,最小质因子就是它本身
for (int j = ; primes[j] <= n / i; j ++ )
{
st[primes[j] * i] = true;
ans+=primes[j];//对于响primes[j] * i这样不是质数的数字,那么primes[j]正好是他的质因子
if (i % primes[j] == ) break;
}
}
}
int main()
{
int n;
cin >> n ;
get_primes(n);
cout << ans << endl;
return ;
}

最新文章

  1. idea开发工具破解地址
  2. 微信第三方平台定时接收component_verify_ticket
  3. ant常用命令
  4. 九度oj 1528 最长回文子串
  5. IOS 沙盒机制 &amp;&amp; 关于document\library\tmp的灵活使用
  6. jsp &lt;%! %&gt; 与 &lt;% %&gt; 区别
  7. Javascript闭包与作用域
  8. Html.DropDownList的用法
  9. Uiautomator--出现报错“urllib3.exceptions.ProtocolError:&lt;&#39;Connection aborted.&#39;,error&lt;10054,&#39;&#39;&gt;&gt;”的解决方式!
  10. 页面跳转时,url 传大数据的参数不全的问题+序列化对象
  11. php中获取当前时间
  12. Redis中的执行命令的过程
  13. Oracle课程档案,第十六天
  14. BBU和RRU具体区别是 什么?
  15. C#基础巩固(2)-Linq To XML创建XML
  16. python三大框架之一flask中cookie和session的相关操作
  17. Oracle性能诊断艺术-读书笔记(脚本dbms_xplan_output截图-非常好的)
  18. PHP:第一章——PHP中常量和预定义常量
  19. catkin-tools
  20. 递增和递减进度条CCProgressTimer

热门文章

  1. .Net笔试考题
  2. ueditor+复制word+图片不能上传
  3. TTTTTTTTTTTTTT poj 1127 Jack Straws 线段相交+并查集
  4. NOI 2019 AFO 记
  5. R_Studio(学生成绩)对两个班级学生成绩进行集合,重新计算学生综合测评成绩并对学生按综合测评成绩进行排名
  6. 客户端框架-MVP
  7. sqlmap自动注入1(Target完整的超级详细 如有错误望指出)
  8. git 指定自己的sshkey
  9. 胜利点20191010-5 alpha week 1/2 Scrum立会报告+燃尽图 03
  10. 清明 DAY 3