iclestu

September 20th, 2012, 05:26 PM

Hey guys,

I am a novice programmer at best but i do like to play around with the problems on projecteuler.net. I concentrate on getting some 'general' algorithm to work out the answer and am not overly concerned about asthetics as (usually!) i am the only one to read my code and i am not generally picky about going about things the 'wrong way' unless they stop my code from working....

I am working on problem 243 and have a little python function, to which i pass an integer, d, and a list of the prime divisors of d, prmList and the function returns the number of integers between 1 and d-1 which is co-prime with d.

Given that even with efficient gcd algorithms this was too slow to implement directly I am approaching it in a similar way to the sieve of erothasenes for primes in that have an array of bool values (of length d) initialised at True (except d[1] as 1 is always coprime with d). I then cycle through the primes in prmList changing every multiple of it to False in the array then return the sum of the 1's in the array....

Hope that makes sense! Here is the code:

def resNum1(d,prmList):

isRes=[0,1] ####

for i in range(2,d): ### these lines just initialise array

isRes.append(1) ###

for i in prmList:

tmp=i

while tmp<d:

isRes[tmp]=0

tmp+=i

return sum(isRes)This works great when I pass it all values up to (2*3*5*...*19,[2,3,5,...,19])

but it crashes my whole system if i pass it the values (2*3*5*...*19*23,[2,3,5,...,19,23])

Why?

I know I am giving it much more work (23 times more) but when i hit ctrl+esc to try and kill it my system monitor suggests its taking up 1.2Gb of memory!!!

How it that possible? Surely that array (well, i know its actually a list) of bools cant take up THAT much space?

any gurus able to enlighten me as to whats going on?

I am a novice programmer at best but i do like to play around with the problems on projecteuler.net. I concentrate on getting some 'general' algorithm to work out the answer and am not overly concerned about asthetics as (usually!) i am the only one to read my code and i am not generally picky about going about things the 'wrong way' unless they stop my code from working....

I am working on problem 243 and have a little python function, to which i pass an integer, d, and a list of the prime divisors of d, prmList and the function returns the number of integers between 1 and d-1 which is co-prime with d.

Given that even with efficient gcd algorithms this was too slow to implement directly I am approaching it in a similar way to the sieve of erothasenes for primes in that have an array of bool values (of length d) initialised at True (except d[1] as 1 is always coprime with d). I then cycle through the primes in prmList changing every multiple of it to False in the array then return the sum of the 1's in the array....

Hope that makes sense! Here is the code:

def resNum1(d,prmList):

isRes=[0,1] ####

for i in range(2,d): ### these lines just initialise array

isRes.append(1) ###

for i in prmList:

tmp=i

while tmp<d:

isRes[tmp]=0

tmp+=i

return sum(isRes)This works great when I pass it all values up to (2*3*5*...*19,[2,3,5,...,19])

but it crashes my whole system if i pass it the values (2*3*5*...*19*23,[2,3,5,...,19,23])

Why?

I know I am giving it much more work (23 times more) but when i hit ctrl+esc to try and kill it my system monitor suggests its taking up 1.2Gb of memory!!!

How it that possible? Surely that array (well, i know its actually a list) of bools cant take up THAT much space?

any gurus able to enlighten me as to whats going on?