pythonprime-factoring

Prime factors in python


I am looking for prime factors of 2500 with the code below, but my code only prints 2 currently and I am unsure why this is the case.

no = 2500
count = 0
# Finding factors of 2500
for i in range(1,no):
    if no%i == 0:
    # Now that the factors have been found, the prime factors will be determined  
        for x in range(1,no):
            if i%x==0: 
                count = count + 1
            """Checking to see if the factor of 2500, itself only has two factor implying it is prime"""  
                if count == 2:
                    print i

Thanks


Solution

  • using sieve of eratosthenes to first generate list of primes:

     from math import sqrt
    def sieve_of_eratosthenes(n):
        primes = range(3, n + 1, 2) # primes above 2 must be odd so start at three and increase by 2
        for base in xrange(len(primes)):
            if primes[base] is None:
               continue
            if primes[base] >= sqrt(n): # stop at sqrt of n
                break
            for i in xrange(base + (base + 1) * primes[base], len(primes), primes[base]):
                primes[i] = None
        primes.insert(0,2)
        sieve=filter(None, primes)
        return  sieve
    
    def prime_factors(sieve,n):
        p_f = []
        for prime in sieve:
            while n % prime == 0:
                p_f.append(prime)
                n /= prime
        if n > 1:
            p_f.append(n)
        return p_f
    sieve = sieve_of_eratosthenes(2500)
    print prime_factors(sieve,2500)