Trying to get prime factorization for Sieve of Eratosthenes

Question

I have a file of numbers that i need the prime factorization for. so it should look like: "250,000,001 = 148,721 * 41 * 41" on the output. my code so far is:

factors = [2, 5, 7, 9, -1]

def primeFactors(x, primes):
    myList = []
    myFile = open('ten.txt', 'r', encoding = 'utf-8')
    for x in myFile:
        x = (int(x) % f for f in factors)
        myList.append(x)
        print(myList)

primeFactors(open('ten.txt', 'r', encoding = 'utf-8'), factors)

With the output being (generator object (genexpr) at 0x100647870)

what do i need to do to even get the factors listed out?

Edit i guess i should mention that this is completely wrong i realize that. but here i made some edits to my code. I am intending to print out the factorization using factors under 10,000,000.

factors = [2, 3, 5, 7, 11, -1]
n = 10000000
primes = list()
multiples = set() #creates list of primes out of 10,000,000
for i in range(2, n+1):
    if i not in multiples:
        primes.append(i)
        multiples.update(range(i*i, n+1, i))

def primeFactors(x, primes):
    factors = [f for f in primes]    #trying to get the factorization for 25,000,001
    if x % factors == 0:
        return primes
primeFactors(25000001, primes)

the problem is that i do not know how to get my x value, 25000001 to be divided one by one until it comes out without a remainder into the aforementioned factorization in the first post.

does that make sense?

What exactly were you hoping to get out of `x = (int(x) % f for f in factors)`. It's pretty clear that this is wrong; what's not clear is how to fix it, because I have no idea what you were intending. I think what you actually want is an `if` statement, not an assignment, in the first place, but it's hard to see where you were trying to go here. — abarnert, Aug 26 '14 at 22:34
Why are you sending a file handle to the function and then re-opening the file again? Also encoding is not a valid argument for open. See: https://docs.python.org/2/library/functions.html#open — user3885927, Aug 26 '14 at 22:37
And for python Sieve of Eratosthenes see this related SO item that was first in my google search! http://stackoverflow.com/questions/3939660/sieve-of-eratosthenes-finding-primes-python — user3885927, Aug 26 '14 at 22:40

dwurf · Answer 1 · 2014-08-26T22:38:32.173

0

Try this:

myList.extend(x)

instead of:

myList.append(x)

edited Aug 26 '14 at 22:38

answered Aug 26 '14 at 22:33

dwurf

12,393
6
30
42

score 0 · Answer 2 · answered Aug 26 '14 at 22:33

Your code does not output what you claim it does.

What you actually get is something like:

[<generator object <genexpr> at 0x1091ee410>]
[<generator object <genexpr> at 0x1091ee410>, <generator object <genexpr> at 0x1091ee440>]
[<generator object <genexpr> at 0x1091ee410>, 
 <generator object <genexpr> at 0x1091ee440>,
 <generator object <genexpr> at 0x1091ee470>]

… etc.

Why?

Well, each x is a generator:

x = (int(x) % f for f in factors)

So, each time through the loop, you add one more generator to the list.

How do you fix it? Well, that depends on what you were intending to do. Did you want to add a list of all those remainders instead of a generator? If so, use […] instead of (…). Did you want to add each of the remainders itself to the list? If so, use myList.extend instead of .append.

Also, you're using the same name, x, for three different things: the first parameter to the function, and the loop variable, and the generator expression that you add to the list. Each time you give it a new value, you lose the old one. That can't possibly be right. But again, I'm having a hard time imagining what you were actually trying to do.

user3666197 · Answer 3 · 2014-08-26T22:39:46.953

0

Change a parameter name x -> par_x as you mismatch the name with for x ...

def primeFactors( par_x, primes ):

You assign to x in the function call many other times -- repair

 for x ...                                          # sets x as a <for> iterator
     anotherVar_x = ( int(x) % f for f in factors)  # sets x again -> anotherVar_x

edited Aug 26 '14 at 22:39

answered Aug 26 '14 at 22:33

user3666197

1
6
50
92

score 0 · Answer 4 · answered Aug 26 '14 at 22:35

if you need to print the numbers computed inside x, I would suggest to use a list comprehension instead of a generator object:

x = [int(x) % f for f in factors]
print(x)

also please note that x inside for x in myFile overrides the x from primeFactors(x, primes), you open the same file 2 times and the code is nowhere near the prime factorization yet.

Trying to get prime factorization for Sieve of Eratosthenes

4 Answers4