Key factors in python

Question

I am looking for basic 2500 odds with the code below, but my code only prints 2 at the moment, and I'm not sure why this is.

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

Answer 1

using an eratosthenes sieve to first generate a 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) 

Answer 2

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

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

In this example, the factors will contain the following list:

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

In particular, for a prime number, the counter will be 1.

Edit: Good, so I misunderstood the question. The list contains only delimiters, not the main factors ... Sorry for the confusion!

Answer 3

Your count variable will only be == 2 times.

 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 basic 2500 odds as a list. If you use only primes from 2 to 2500 instead of the range (2, n), it will be faster. Wikipedia Trial Section