> Well, there are really only a couple of optimizations that you could make.
> That's the nice (bad?) thing about primes - you really only *can* brute
> force a solution. That's why nice things like encryption exist.
Yes, I know that; perhaps I was unclear but my issues with brute force
are for solutions 1 and 2, not solution 3. For instance, problem 2 is:
#By considering the terms in the Fibonacci sequence whose
#values do not exceed four million, find the sum of the even-valued terms.
And my solution is
def fib(n = 4000000):
a, b = 0, 1
while a < n:
a, b = b, a + b
if a%2 == 0: yield a
Which is perfectly fine as a solution, but nowhere near as elegant as
the mathematical solution. Anyway, I digress.
> The less obvious optimization is in reference to primes - you don't actually
> have to check all the way up to N. Or even N/2. You only have to check
> numbers up to the square root of N. This explanation may not be
> mathematically sound, but basically the reason this works is the definition
> of prime: N is divisible only by N and 1. If you divide a number by 2 then
> then the result will be the largest factor (e.g. 100/2 = 50). But as you
> start increasing the divisor then obviously the result has to decrease. The
> point at which these numbers are equivalent? The square root, of course.
I was suspecting there was something like that; my thoughts were
starting to move toward something along those lines. I suppose I'm
just rusty.
> Now, I'm not sure what the time complexity of these two operations is, but
> go ahead and put this line in your isprime:
>
> if n == 11: print("Checked 11... again")
>
> Can you think of a way to compute the primes you need to check only once?
First reaction: "whoa!". That is a lot of redundant calculations. I'm
afraid I'm a bit stumped on this one; one solution that seems to work
is sending the factor to isprime() along with n, and do the for loop
like this:
for x in range(factor, round(sqrt(n))):
But I'm not sure that's actually a good idea or if it just happened to
work in this particular case. As I said, it seems to work but it could
just be a coincidence. Way I see it, I've already tested all the
numbers up to the last factor and so I shouldn't need to test them
again? However, your "if n == 11" line confuses me; after the changes
I never once hit n == 11, which is weird?
Anyway, this is my reworked functions, which are much faster than the
original ones. I really need to learn how to use the timeit module to
see the difference.
from math import sqrt
def isprime(n, factor):
if n == 1:
return False
for x in range(2, round(sqrt(n))):
if n % x == 0:
return False
else:
return True
def factorization(n):
factor = 2
x = 3
while True:
if n % x == 0:
if isprime(x, factor):
factor = x
n = n // x
if n == 1:
return factor
else:
return factor
x += 2
print(factorization(600851475143))
>
> HTH,
> Wayne
--
best regards,
Robert S.
_______________________________________________
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
http://mail.python.org/mailman/listinfo/tutor
