求一道 hust acm解题报告:Prime's Sum Again.
来源:学生作业帮 编辑:大师作文网作业帮 分类:英语作业 时间:2024/09/27 10:20:09
求一道 hust acm解题报告:Prime's Sum Again.
Prime's Sum Again
Description
As is known to all,a prime number is a number which can only be divided by 1 and itself.For example:2,3 and 5 are all prime numbers but 4 and 6 are not,because 4 has another divisor 2,and 6 has two other divisors 2 and 3.
Then the problem is:give you two nonnegative integers L and R,you are asked to tell me the sum of all the prime numbers in the range [L,R).Range [L,R) means all the integers x that L
Prime's Sum Again
Description
As is known to all,a prime number is a number which can only be divided by 1 and itself.For example:2,3 and 5 are all prime numbers but 4 and 6 are not,because 4 has another divisor 2,and 6 has two other divisors 2 and 3.
Then the problem is:give you two nonnegative integers L and R,you are asked to tell me the sum of all the prime numbers in the range [L,R).Range [L,R) means all the integers x that L
你可以考虑打表 打一部分 比如只记录隔上100000的质数(100000不行可以试试别的)
这样l 到r 就可以快速找到[100000a,100000b]中质数的和
然后暴力[l,100000a) (100000b,r] 的质数 再加上去
再问: 求更多细节!
再答: 比如你要求 [1234567,7654321]之间质数的和 预处理,S[x] 便是[1,100000x]之间质数的和 于是可以快速求得[1300000,7600000]的和, S[76]-S[12] 然后暴力悲剧[1234567,1299999],[7600001,7654321]之间的质数 不会超过20万个, 用Miller-Rabin一一检验 也不会超时了
这样l 到r 就可以快速找到[100000a,100000b]中质数的和
然后暴力[l,100000a) (100000b,r] 的质数 再加上去
再问: 求更多细节!
再答: 比如你要求 [1234567,7654321]之间质数的和 预处理,S[x] 便是[1,100000x]之间质数的和 于是可以快速求得[1300000,7600000]的和, S[76]-S[12] 然后暴力悲剧[1234567,1299999],[7600001,7654321]之间的质数 不会超过20万个, 用Miller-Rabin一一检验 也不会超时了
求一道 hust acm解题报告:Prime's Sum Again.
acm Calculate the Sum
一道ACM编程题 求算法思路.
求问一道GRE数学题S is the sum of the first n negative integer power
杭电ACM MAX SUM题目看不懂
acm一道很简单的数论题,求拯救
一道acm水题,求一种高效的算法,
acm 一道水题:Increase and Decrease 求思路
一道简单的acm题目中的一个bug求调试
一道高等数学极限求解题
杭电ACM第2136题Largest prime factor,
一道ACM题目,看不懂