lua - 有没有更快的方法在lua中找到素数？

Question

我正在研究 Project 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

有谁知道找到素数的更多方法，甚至是优化它的方法？我总是试图自己编写代码，但这个真的难倒了我。

无论如何，谢谢!

Answer 1

此代码基于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 个除法非常昂贵。