CODEWITHSUNDEEP
pythonpython-3.xmemoryout-of-memoryexponent
bravoalpha90
bravoalpha90

Reputation: 463

An exponent within my prime numbers program throws a memory error, how do I solve this?

if (2 ** (tester - 1)) % tester == 1:  # Fermat's little theorem      #
    if prime_line.count(tester) == 0:                                 #
        prime_line.append(tester)

I am using a program that takes multiple line inputs of any value or string or combination thereof, and returns any present prime numbers within the set. I am using Fermat's theorem to test whether or not the number is prime in order to minimize processing time. In the aforementioned code, numbers such as 194394788347, having already been stripped of its letters (starting input would be 1943jds9478cxbfhjvbfd8347) creates a memory error when the exponent calculation is made. Is there any way to solve this issue?

Upvotes: 2

Views: 123

Answers (1)

Max
Max

Reputation: 10985

2 ** 194394788347 is an astronomically large number, requiring over 22 GB just to store. Luckily, python contains a function to exponentiate while doing modulus as it goes: pow(base, exp, mod).

if pow(2, tester - 1, tester) == 1:

This is also much faster, as none of the intermediate numbers are ever much larger than the modulus.

Upvotes: 6

Related Questions