Problem 1490 --关于最大公约数的疑惑

1490: 关于最大公约数的疑惑

"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $124$ 正确数量 $16$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 数论
小光是个十分喜欢素数的人,有一天他在学习最大公约数的时候突然想到了一个问题,他想知道从1到n这n个整数中有多少对最大公约数为素数的(x,y),即有多少(x,y),gcd(x,y)=素数,1<=x,y<=n。但是小光刚刚接触最大公约数,不能解决这个问题,于是他希望你能帮助他解决这个问题。
一个整数N  (1<=N<=10^5)
(x,y)的个数
5
5
(2,2) (2,4) (4,2) (3,3) (5,5)

推荐代码 查看1490 所有题解 上传题解视频得图灵币

本题记录 用 户(点击查看用户) 运行号(点击购买题解) 时 间
算法最快[$0 $ms] 秦磊系靓仔 820884 2022-03-14 21:03:03
内存最少[$0 $KB] yaoking 613434 2020-09-29 13:00:04
第一AC webturing 247195 2018-05-17 08:32:05
第一挑战 汪志敏@计算机科学与技术161 37281 2016-12-06 07:41:01

赛题来源/所属竞赛 2014 Anhui College Student Programming Contest N/A

竞赛编号 竞赛名称 竞赛时间 访问比赛
1331 图灵2019五一高级算法集训营:数学与数论专题 2019-05-01 09:00:00 请登录
1077 2014安徽省ACM程序设计大赛 2017-04-25 09:00:00 请登录