[Tutor] [Edu-sig] collection of ACM programming problems (fwd)

Joel Ricker joejava@dragoncat.net
Thu, 11 Jan 2001 19:22:59 -0500

>> On 11/1/01, Remco Gerlich wrote about 'Re: [Tutor] [Edu-sig]

>But 2385/53 = 45, and 53 is a prime number. So that's not even an ugly
>number itself.
>Ugly numbers are the numbers that have 2, 3 and 5 as their *only* prime
>factors. Numbers of the form 2^x*3^y*5^z.
>Made the same mistake myself at first :)

My first attempt was pretty bad as well.  Had  to think long and hard about
exactly what prime factorization was. Come to think of it, I didn't do so
good on the prime factorization problem I had to do when I was in school.
Back to work I guess.

Remco, you mentioned before you worked on a prime number program.  Here's a
challenge to you if you or anyone else is interested.  I assume you took the
normal route of testing each number against an increasing number until
either it divides evenly or gets larger than half the tested number.  Well
try doing a routine that finds a list of prime numbers, say 1 to 1000 using
multiplication instead. Its faster and actually increases speed as it tests
(ie, the number of calculations to test to see if 500 is prime is fewer than
the number of tests to see if 250 is prime).

Joel Ricker     joejava@dragoncat.net     Just Another Python Hacker
I have been Perl-Free for 6 Days, 21 Hours, 26 Minutes, and 4 Seconds.

>Hmm. Math. Maybe this belongs over on python-list...
>Remco Gerlich
>Tutor maillist  -  Tutor@python.org