CODEWITHSUNDEEP
lua
Mr Chikn
Mr Chikn

Reputation: 133

Is there a faster way to find primes in lua?

I am working on Project Euler, and my code is just taking way too long to compute. I am supposed to find the sum of all primes less than 2,000,000 , but my program would take years to complete. I would try some different ways to find primes, but the problem is that I only know one way.

Anyways, here is my code:

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

Does anyone know of any more ways to find primes, or even a way to optimize this? I always try to figure coding out myself, but this one is truly stumping me.

Anyways, thanks!

Upvotes: 3

Views: 327

Answers (1)

Alain Merigot
Alain Merigot

Reputation: 11557

This code is based on Sieve of Eratosthenes.

Whenever a prime is found, its multiples are marked as non-prime. Remaining integers are primes.

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)

As an optimization, even numbers are never considered. It reduces array size and number of iterations by 2. This is also why considered multiple of a found prime are (2k+1)*prime.

Your program had some bugs and computing n^2 divisions is very expensive.

Upvotes: 2

Related Questions