Friday, November 9

python and large numbers

Well ... I was getting bored ten minutes ago, and I wanted to see if python supports large numbers. So, I created a method that would generate a prime number at every iteration, ran it twenty times, and I got this:

9134 [lots of digits removed as per Mrs. Anonymous request; to see the full number, run the python code, below] 4420807

So ... can anyone tell me if it's really a prime number?

Logically, it should be; This is the code:

primes = [1]

def some_prime():
candidate = 1
for i in primes:
candidate *= i
candidate += 1

for i in range(1, 20): some_prime()
print primes[len(primes)-1]

Thanks :)


Anonymous said...

This looks more like an error code than a prime number :D. Anyway, i did not understand that line "candidates *=i". Shouldn't there be a check that the current candidate does not divide with any previous/2 + 1 number? This algorithm is more than i can handle at this (continuous) moment :)) But Phyton was never on my CV, so it's probably me.
Anyway, what i wanted to say is please, (re)move that prime number (wannabe) :P because it shadows the good stuff.
...and it's mrs Anonymous ;).

utnapistim said...

Done :)

The algorithm idea relies on the antique demonstration that there is an infinite number of primes.

The demonstration is a Reductio ad absurdum (I have no idea how to pronounce it in english, but in latin it sounds inteligent enough ;) ).

Basically, you postulate that the number of primes is finite, then compute the product of all the primes, and add one to the result. This will result in a new prime (doesn't divide by any of the prime numbers), so your initial postulation should be false (i.e. the total number of primes is infinite).

What I did was consider 1 as the first prime, then for generating others, just compute the product of all the primes in the list, add one to the result, and add the result to the list, as a new prime.

Not all primes are generated this way (5 for example is not, nor is 11), but I got to an impressive number in 20 iterations.