Question

So I finally managed to work out a prime number calculator for PS1. My first try was a non-perfect-square calculator oddly enough.

intersleft = 1992
x = 3
n = 3
while(intersleft>0):
if(x%n == 0) and(x>n):
x = x+2
n = 3
if(x%n > 0):
n = n+1
if(x == n):
##print (x)
intersleft = intersleft - 1
n = 3
if(intersleft>0):
x = x + 2
print ('finished', x)

It took about 20 seconds to finish. How does it look to you guys?

Answer 1

Gah!!! Make that 1992 a 1998.

Answer 2

ooops, your code seems to print odd numbers, not primes...
i do not catch the spirit of your algorithm: maybe you can try and explain it in words: it would help to understand the code!

Answer 3

The code works primes perfectly for me. I checked, and all the numbers it prints ARE prime. The code works by running through a list of integers one at a time represented by N and testing to see if they are a factor of X. If so, then X is not prime. If no values of N are factors of X, then X is prime.

~~~~~~~
I have a variable X which is a possible prime, and a variable N which is just positive integers. I have X starting at 3 because 2 is the only even prime and 3 comes after. I have N starting at 3 because it must start less than or equal to X, and 2 would only cause more work (explained later).

I have a variable "itersleft" which I use to tally the numbers of iterations left to be done. As long as this number is greater than zero, the nested operations will be executed.

If at any point X is divisible by any value N which does not equal X, then X cannot be prime by definition. I increase X by a value of 2 to keep it odd (since all even numbers are divisible by 2) and reset N to the lowest potential factor (3).

I am using the % operation to see if when X is divided by N there are any remainders. If there are, that means that N was not a factor of X, so I increase N by a value of 1.

If X == N, that means than N has cycled through all values between 3 and X without any of them being a factor of X. This would mean that X is prime. In that case, the number of iterations is reduced by 1 (since we found a prime) and N is reset. The nested "if" operation is to see if there are any more iterations left. If there are, then X is raised to the next potential-prime-number value. If not, then we have reached the number of primes to find as defined by the initial value of "itersleft."

The last bit is printing a string "finished" followed by the final value of X. Should you be wanting a complete list of primes, the earlier print function in line 11 will serve that function.

Answer 4

oooook, found my bug: when i copied and pasted your code to run it, i lost the indent in the last if - i found it checking against the verbal explanation :)
(to avoid this happening, one good solution is to paste your code on
http://codepad.org/
which nicely preserve indents when you copy and past. )

Answer 5

(paste your code on codepad, and then post the link here, i meant!)

Answer 6

http://codepad.org/QeiWNrHE