Memory problem issue on prime number's exercise

Exercism
1

Hi, first of all sorry for my bad English. I’m new here with the python track, have done all exercises till number 59 and it’s the first time I got stuck withouth resolving it on my way, so I’m a bit desperate here looking for help on this exercise.

I’m having a memory problem issue when running the tests and that’s new to me, been trying to solve this problem on different ways but don’t know what other things I can do.
My solution pass all the tests except for the largest prime number of 11 digits. I think I’ve achieved some optimization on the solution using an algorithm similar to the Eratostenes sieve for identifying all the prime numbers till the given number, and then searching for the prime numbers for that number.

I have tried using sets instead of lists but then it’s required a lot of time for running the test and it has never ended because it runs out of time and when I delete the time restriction on the test my computer looks like it’s going to explode after some minutes running.

self = <prime_factors_test.PrimeFactorsTest testMethod=test_factors_include_a_large_prime>

  self.assertEqual(factors(93819012551), [11, 9539, 894119])

prime_factors_test.py:47:

prime_factors.py:18: in factors
primes = prime_sieve(value)

n = 93819012551

def prime_sieve(n):

  sieve = [True] * ((n-1)//2 + 1)  # Only odd numbers till n

E MemoryError

prime_factors.py:2: MemoryError
====================================================================================== short test summary info =======================================================================================
FAILED prime_factors_test.py::PrimeFactorsTest::test_factors_include_a_large_prime - MemoryError
==================================================================================== 1 failed, 11 passed in 0.87s ====================================================================================

And this is the code, hope anyone can help me. I’m really stuck into this, hope that someone can give me some tips or a hint to resolve this. Thanks in advance!!!

def prime_sieve(n):
sieve = [True] * ((n-1)//2 + 1)
primes = [2]

for i in range(3, int(n**0.5) + 1, 2):
    if sieve[(i-1)//2]:
        primes.append(i)
        for j in range(i*i, n+1, 2*i):
            sieve[(j-1)//2] = False
            
for i in range((int(n**0.5) + 1) | 1, n+1, 2): 
    if sieve[(i-1)//2]:
        primes.append(i)
        
return primes

def factors(value):
primes = prime_sieve(value)
result =

for prime in primes:
    while value % prime == 0:
        result.append(prime)
        value //= prime
        
return result
2

When n has 11 digits, your sieve is going to huge and you probably don’t have that much memory on your machine. The trick here is that n cannot have two prime factors both greater than sqrt(n). So if you find all of the factors <= sqrt(n), whatever is left must be prime. This means that you can use a much smaller sieve.

3

OMG thanks!! I’ve got the solution finally… It’s incredible how I was complicating things, the community solutions are so simple…