Programming Assignment: Prime Factorization

Last night the Badb had to find the prime factorization of a number. Thrill moment! This is exactly the problem I once wrote a computer program to solve and wound up entering that program in the school science fair. That was pretty cool.

Back when I had to solve this problem, my computer had a pretty severe limitation within its BASIC interpreter: the highest integer value it could deal with was 65,535. The clock speed on the CPU was pretty darned slow, as well. These meant that any program I wrote had to be pretty efficient if I wanted to be able to interact with it — I could feel myself aging while I waited for the computer to count to 100 — and I didn’t have to worry about really huge data structures. When the biggest array was guaranteed to hold fewer than 100,000 items, FOR..NEXT loops were not very scary.

Okay, enough reminiscing. Here’s the assignment: write a BASIC program that will accept a user’s input of a positive integer greater than 1 and less than 65,536. The program will output the prime factors of the number. The program must guard against empty, non-numeric, and out-of-range values. If the user inputs a value that does not meet the acceptance criteria then the program must print out an error message and prompt once again for input. After writing out the prime factorization of the number, the program should ask the user whether to factor another number or to exit, and then behave appropriately.

Here are some hints:

• a sieve of Eratosthenes would probably be a good place to start to get a bunch of prime numbers
• Any factor of a number that is greater than the square root of that number is, by necessity, part of a pair of factors — and the other half of that pair is less than the square root of the number.
• The modulus operator (mod) might be helpful.
• Try using pencil and paper to draw a flowchart for how to solve the problem. Start with boxes that represent big steps (“get user input”, “compute prime numbers”, etc.) and then explode the boxes until each box represents a line of actual code. This can seem kind of extreme, but it totally works and it keeps you from having to remember everything at once.

I’m gonna make some time to try to write this program myself, but it’d be super cool if any of the three of you people reading this could beat me to it. I’d be really proud!