题目
Problem 10: Summation of primes
The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
Find the sum of all the primes below two million.
第一个解答
两百万以下的素数的和是多少？使用 Haskell 解答如下：
isPrime n = null [ x | x <- [3,5..ceiling $ sqrt $ fromIntegral n], mod n x == 0 ]
main = print $ 2 + (sum $ takeWhile (<2*10^6) $ filter isPrime [3,5..])
这个程序的运行时间是 14.426 秒。
第二个解答
稍做改进后的 Haskell 程序：
small p (x:xs) = if p x then [] else x : small p xs
primes = 2:3:5:[ n | n <- [7,9..], all (\m -> 0 /= mod n m) $
small (>ceiling(sqrt $ fromIntegral n)) primes ]
main = print $ sum $ takeWhile (<2*10^6) primes
这个程序的运行时间是 6.171 秒。
第三个解答
其实 Haskell 语言的函数库中有一个 primes 列表，可以直接使用：
import Math.NumberTheory.Primes.Sieve
main = print $ sum $ takeWhile (<2*10^6) primes
这个程序的运行时间是 0.146 秒。
以上三个程序均改写自“欧拉计划：007. 第10001个素数”，具体工作原理可参见该文。
参考资料
- Project Euler: 010_overview.pdf
- HaskellWiki: Prime numbers
- Hackage: arithmoi: Efficient basic number-theoretic functions. Primes, powers, integer logarithms.
- Haskell: Math.NumberTheory.Primes.Sieve
- LiteratePrograms: Sieve of Eratosthenes (Haskell)
- Wikipedia: Prime number theorem
- 图灵社区：欧拉计划：003. 最大素因子
- 图灵社区：欧拉计划：007. 第10001个素数
private static boolean isPrime(int ANum) {
// if (ANum == 2)
// return true;
// if ((ANum < 2) || (ANum % 2 == 0))
// return false;
int nSqrt = (int) Math.sqrt(ANum);
for(int i = 3; i <= nSqrt; i += 2){
if (ANum % i == 0)
return false;
}
return true;
}
public static final int Max_Value = 2000000;
public static void main(String[] args) {
long begin = System.currentTimeMillis();
long LSum = 2;
for(int i = 3; i <= Max_Value; i += 2){
if (isPrime(i))
LSum += i;
}
System.out.println(LSum);
System.out.println(System.currentTimeMillis() - begin);
}
}
这个不能用于2百万的运算因为数字量太大了 这个的思路是 一个素数是素数当他不能除尽任何一个比他小的素数
def prime(s: Stream[Int]): Stream[Int] = {
s match {
case head #:: tail => head #:: prime(tail.filterNot(_ % head == 0))
case _ => Stream.empty
}
}
def main(args: Array[String]): Unit = {
println(prime((2 to 100).toStream).sum)
}
好 能用的解法是：
def main(args: Array[String]): Unit = {
// println(prime((2 to 100).toStream).sum)
val begin = System.currentTimeMillis()
var count=0
for( i <- 2 to 2000000) {
if(!(2 until Math.sqrt(i).toInt+1).exists(i % _ ==0)){
count = count + i
}
}
val end = System.currentTimeMillis()
println(count)
println(s"time:${end-begin}")
}
}
2s左右结束
#-_-无耻一行流
@time result=sum(primes(2000000))
@show result
#=
0.037111 seconds (2.35 k allocations: 2.632 MB)
result = 142913828922
[Finished in 4.3s]
=#