This is a read-only snapshot of the ComputerCraft forums, taken in April 2020.
Himself12794's profile picture

Determining Prime

Started by Himself12794, 10 March 2014 - 06:22 AM
Himself12794 #1
Posted 10 March 2014 - 07:22 AM
For a project I'm working on, I need to find the sum of the first 1000 prime number.
I know the answer should be: 3682913
But instead I'm getting: 3690837
The code I use is below.

function primes(n)
    if n<2 then
	    return false
    elseif n==2 then
	    return true
    elseif n%2==0 or n%3==0 then
	    return false
    else
	    for i=3, math.ceil(n^0.5) do
		    if n%i==0 then
			    return false
		    end
	    end
    end
    return true
end

local count=0
local number=2
local sum=0
    
while count<1000 do
    if primes(number) then
	    count=count+1
	    sum=sum+number
    end
    number=number+1
end
print(sum)
I ran a trace and found that just one sum down, I get, 3682913, which is just 3 off. Not sure if my problem has to do with determining primes in the first place, limitations of lua, or just simple errors. Help is appreciated.
twormtwo #2
Posted 10 March 2014 - 10:40 AM
You just forgot that 3 is a prime number. And since 3%3=0, it returns false for 3.
Himself12794 #3
Posted 10 March 2014 - 02:05 PM
You just forgot that 3 is a prime number. And since 3%3=0, it returns false for 3.
Ah! So it is. Thanks alot!
theoriginalbit #4
Posted 10 March 2014 - 02:13 PM
I ran a trace and found that just one sum down, I get, 3682913, which is just 3 off.
as for this problem, its all to do with the loop. there's multiple ways to change it so that it works, the way I did it in my test before was the following.


repeat
  if primes(number) then
    count=count+1
    sum=sum+number
  end
  number=number+1
until count == 1000
Himself12794 #5
Posted 10 March 2014 - 02:16 PM
I ran a trace and found that just one sum down, I get, 3682913, which is just 3 off.
as for this problem, its all to do with the loop. there's multiple ways to change it so that it works, the way I did it in my test before was the following.


repeat
  if primes(number) then
	count=count+1
	sum=sum+number
  end
  number=number+1
until count == 1000
That does seem simpler, though my initial problem was when trying to determine a prime number faster, I forgot to include 3. That way it went over one extra not including 3. I did not know about the repeat function. Seems to work like do…while.
GopherAtl #6
Posted 10 March 2014 - 06:32 PM
yeah, repeat…until is just a post-condition loop where while is a pre-condition, so repeat always runs at least once, even if the condition is initially false. Otherwise identical.

on optimization, I'm not sure if you gain yourself much with the pre-tests for <2 (which you never pass it anyway), and %2 and %3 (which would be the first and second tested in the loop anyway)

If you want it to run faster, consider building an array of the primes as you find them, and only check against those, instead of against all integers, within the 2 to n^.5 range. A lot less tests that way!

:edit: huh, just tried this (for the hell of it) and I think the table operations of checking an existing list of primes are actually making it /slower/. Which is surprising to me. Are lua tables actually that slow? further testing requried, but I won't derail the thread with it….
Edited on 10 March 2014 - 05:41 PM