我正在研究Euler项目,而我的代码花费的时间太长了,无法进行计算。我应该发现所有素数的总和小于2,000,000,但是我的程序将需要数年才能完成。我会尝试一些不同的方法来找到素数,但是问题是我只知道一种方法。

无论如何,这是我的代码:

sum=2
flag=0
prime=3
while prime<2000000 do
    for i=2,prime-1 do
        if prime%i==0 then
            flag=1
        end
    end
    if flag==0 then
        print(prime)
        sum=sum+prime
    end
    prime=prime+1
    flag=0
    if prime==2000000 then
        print(sum)
    end
end


有人知道更多找到素数的方法,甚至优化它的方法吗?我总是试图弄清楚自己的编码,但是这个确实让我很沮丧。

无论如何,谢谢!

最佳答案

此代码基于Sieve of Eratosthenes

每当找到质数时,其倍数就会标记为非质数。剩余的整数是质数。

nonprimes={}
max=2000000
sum=2
prime=3
while prime<max do
   if not nonprimes[prime] then
      -- found a prime
      sum = sum + prime
      -- marks multiples of prime
      i=prime*prime
      while i < max do
         nonprimes[i] = true
         i = i + 2*prime
      end
   end
   -- primes cannot be even
   prime = prime + 2
end
print(sum)


作为优化,从不考虑偶数。它将数组大小和迭代次数减少2。这也是为什么认为发现的质数的倍数为(2k + 1)*质数的原因。

您的程序存在一些错误,计算n ^ 2除法非常昂贵。

10-07 17:02
查看更多