Есть ли более быстрый способ найти простые числа в Луа?

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

Этот код основан на Сите Эратосфена .

Всякий раз, когда найдено простое число, его множители помечаются как не простые.Оставшиеся целые числа - простые числа.

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 делений очень дорого.