[Tutor] project euler prime factorization problem

[bob gailer]

  On 8/29/2010 3:08 AM, Nick wrote:
>
> The prime factors of 13195 are 5, 7, 13 and 29.
>
> What is the largest prime factor of the number 600851475143 ?
>
> #don't forget 2,3,5,7.  this function doesn't deliver those as output.
>
> def is_prime(b):  #checks a number greater than 7 to see if it is 
> prime and returns if is.
>     if b % 2 != 0 and b % 3 != 0 and b % 5 != 0 and b % 7 != 0:
>         print b,
> def factor(num):
>     x = num
>     b = 1
>     c = num
>     while b <= c:       #starts at 1 and searches all the numbers up 
> to the number you put in
>         if x % b == 0:
>             is_prime(b)
>             b += 1
>         else:
>             b += 1
>
> print "Don't forget to consider primes 2, 3, 5, and 7\n"
>
>
> #600851475143
>
> #shows what numbers in given range are prime
> '''
> def is_prime(b):
>     return [2,3,5,7] + [x for x in xrange(3, 10000, 2) if x % 2 != 0 
> and x % 3 != 0 and x % 5 != 0 and x % 7 != 0]
> '''
>
> I'm looking for some help with this problem.  I realize my code is 
> inefficient for such a big number, and also I'm not quite sure it 
> works perfectly in and of itself.

Did you test the program? That is one way to tell whether it works 
perfectly. What you showed above will do one visible thing - it will 
print "Don't forget to consider primes 2, 3, 5, and 7\n". The rest is a 
somewhat confusing collection of function definitions and comments. You 
never call the functions so nothing else will happen.

As Alan said - research prime factors to see how others approach it.
>
> My current reasoning was something of this sort:  Find all the factors 
> of a number, then reduce them to just the prime factors

Very inefficient. IMHO the proper way is to generate a list of all the 
prime numbers up to the square root of 600851475143, then test each 
(starting with the largest and working down) till you discover a factor. 
That then is the answer.

There are many published algorithms for generating primes.

> and you can then multiply them together to get that number thus having 
> the prime factors.  I need a lot of help haha.  Thanks in advance 
> everyone.  If anyone has a good resource to point me to other than the 
> open book project and dive into python it would be much appreciated. 
>  Would it be useful for me to buy a book, and if so what are some 
> easily accessible ones?  I feel dive into python is just too advanced 
> for me.  I understand a lot of the teachings, but the examples seem 
> unwieldy and esoteric.

-- 
Bob Gailer
919-636-4239
Chapel Hill NC

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/tutor/attachments/20100829/60ad76b5/attachment.html>