Prime factors in python

Question

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

The algorithm doesn't make too much sense to me, care to explain it? — filmor, May 02 '14 at 07:34
possible duplicate of [Python Finding Prime Factors](http://stackoverflow.com/questions/15347174/python-finding-prime-factors) — sundar nataraj, May 02 '14 at 07:36
the only time i%x ==0 is at the start of your second for loop when i and x are both = 1 — Padraic Cunningham, May 02 '14 at 07:45

Padraic Cunningham · Accepted Answer · 2014-05-02T08:55:56.507

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)

Chris · Answer 2 · 2014-05-04T01:12:51.080

I'm sorry I don't really understand your algorithm but if you're interested in finding the factors of a number, you could the following (based on your algorithm) :

no = 2500
factors = [i for i in range(1,no) if no % i == 0]
count = len(factors)

In this example, factors will hold the following list :

[1, 2, 4, 5, 10, 20, 25, 50, 100, 125, 250, 500, 625, 1250]

In particular for a prime number, count will be 1.

Edit: Ok, so I did misunderstand the question. The list contains merely the dividers and not the prime factors... Sorry for the confusion!

score 0 · Answer 3 · answered May 02 '14 at 08:04

Your count variable will be only once == 2.

n = 2500
prime_factors = []

for p in range(2,n):
    if p*p > n: break
    while n % p == 0:
        prime_factors.append(p)
        n /= p
if n > 1: prime_factors.append(n)

print prime_factors

You get the prime factors of 2500 as a list back. If you use only the prime numbers from 2 to 2500 instead of range(2,n) it'll be faster. Wikipedia - Trial division

Prime factors in python

3 Answers3

Linked