On Sun, 22 Aug 2010 03:47:21 pm Nick wrote: > Thanks so much Steven. I get it all except I don't think I see the > pattern. I see that we're already covering those higher factors > since they're divisble by 2, 3, 5, etc. I'm just not connecting the > final dot with the square root of n. It's almost there in my mind! > I just need a little more of a push!
Okay, let's consider an example: n = 100. We start checking factors of 100 by dividing by 1, 2, 3, 4, ... and so on: 1 * 100 = 100 2 * 50 = 100 4 * 25 = 100 5 * 20 = 100 ... As the first factor increases, the second factor decreases proportionally. It has to, because the product is always 100. So, if you have one pattern going up (1, 2, 4, 5, ...), and another pattern going down (100, 50, 25, 20, ...), there must be a point where the two patterns cross! That point is at the square root: 10 * 10 = 100 Once you pass the square root, any factors you find will be the same as the factors you've already seen, only reversed: 20 * 5 = 100 # Seen this one before as 5*20. Not all numbers have a whole number square root, but the principle still holds: 1 * 120 = 120 2 * 60 = 120 3 * 40 = 120 4 * 30 = 120 5 * 24 = 120 6 * 20 = 120 8 * 15 = 120 10 * 12 = 120 10.9545 * 10.9545 = 120 12 * 10 = 120 <=== already seen this one! > Also I can write a program that > tests whether the number is a factor of 2, 3, 5, 7, but I think > you're trying to point to me that this is cumbersome and not > necessary. Sort of. I'm not suggest that you create lists of multiples of 2, 3, 5, 7 etc, and then cross off non-primes by checking to see if they are in one of those lists. That truly would be cumbersome and slow. But the two problems are similar. For simplicity, let's ignore 2 as a prime, and only think about odd numbers: (1) For each odd number N between 3 and (say) 1000, check if it is a multiple of 3, 5, 7, 9, ... and IF SO, put it in the list "nonprimes". versus: (2) For each odd number N between 3 and (say) 1000, check if it is a multiple of 3, 5, 7, 9, ... and IF NOT, put it in the list "primes". See, they are very nearly the same problem. The tricky bits are: * dealing with 2 is a special case; * you don't want to exclude (say) 3 from being a prime because it is divisible by 3; and * you can stop testing at square-root of N. -- Steven D'Aprano _______________________________________________ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
