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

Mouth

The algorithm doesn't make too much sense to me, care to explain it? – Elfland

possible duplicate of Python Finding Prime Factors – Avast

Bad indentation, you only print something if count==2... – Deragon

Shouldn't the second for loop be indented further? – Throughput

@Elfland I hope it is clearer – Mouth

@Throughput I've made the required indentations now. Thanks. – Mouth

the only time i%x ==0 is at the start of your second for loop when i and x are both = 1 – Hysterogenic

Answer 1

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)

Hysterogenic

Answer 2

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!

Throughput

Answer 3

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

Plott

Answer 4

I used 6k+1 and 6k-1 to speed things up some. They are the maybe primes from 5 to sqrt(n)+1:

def prime_factors(n):
    p_f = []
    while n % 2 == 0:  # got any 2's
        p_f.append(2)
        n //= 2
    while n % 3 == 0: # got any 3's?
        p_f.append(3)
        n //= 3
    for p in range(5,int(n**.5),6): # go fish
        if p*p > n: break
        while n % p == 0:  # 6k-1 5,11,17,23 ...
            p_f.append(p)
            n //= p
        while n % (p+2) == 0: # 6k+1  7,13,19,31...
            p_f.append(p+2)
            n //= (p+2)
    if n > 1: p_f.append(n)
    return p_f

n=4231432143534546
#n=78359854509899
f = prime_factors(n)
print(f"Prime factors {f}")
print(f"{n:,}",'is Prime' if len(f)==1 else 'is Composite'  ) 

Output:

$ python prime_fact_stk.py 
Prime factors [78359854509899]
78,359,854,509,899 is Prime

$ python prime_fact_stk.py 
Prime factors [2, 3, 3, 3, 78359854509899]
4,231,432,143,534,546 is Composite

Bremerhaven