1. ## Integer Factorization

Hi all,

again another question hoping to find it's answer on this forum. The question is related to a program I recently made, a program for integer factorization.

I won't be posting the whole code here, since it's six pages long, and half of that is only "ifs" and "switches" so I never get output in the form of, say, "5^0", or "2 ^1" and such. The basic way the program works:

1. Asks user for the number they want to factorize
2. Generates primes up to that number into an 2D array (second dimension explained later), and at the same time checks if the entered number is prime.
3. Divides by two while possible, incrementing a variable every time it does so.
4. Does the same thing except with division by three.
5. If, after division by two and three, the result is one, it prints out something like "2^2 x 3"
6. If after division by two and three, the result isn't one, division continues with the primes in the array generated at the beginning. Whenever a prime is a divisor, the second dimension, which is by default 0, is incremented. This is done while possible.
7. The primes that have a value bigger than 0 in the second dimension of the array are transfered to a new array, which is then printed out. I have the same switches/ifs etc. to ensure proper form

The complete source code is included in the attachment. The code works fine, except for one thing, that being that it can't factorize numbers above thirty two thousand something. I can't remember the exact number. I have a feeling that is has something to do with the number of elements an array can have, but I'm not sure. I've tried changing the data type, but even when I use an unsigned long long int it won't change anything.

Help is appreciated

2. Methinks you can probably do that in much less than 6 pages of code.

3. Originally Posted by arpsmack
Methinks you can probably do that in much less than 6 pages of code.
That depends on the font size!
Yeah I think 1-2 pages would be more like it.

4. Of course you can. As I said, like half of that, and I just checked and it's a little more, is just ifs and switches that have no use other than visual appeal. Check for yourselves, I just added the source ;-)

Any idea however on what to do with the problem I'm having?

5. Instead of generating all the possible prime factors, it would be less memory intensive to find the prime factors on the fly.

A possible algorithm would be along the lines of:
Code:
```n = number entered by user
sqrt_n = sqrt(n)
i = 2
while n > 1 and i <= sqrt_n
if n is divisible by i
add i to list of prime factors
count = 1
n = n / i
while n is divisible by i
increment count
n = n / i
add count to list of prime factor counts
increment i
if n > 1
add n to list of prime factors
add 1 to list of prime factor counts```

6. That program does not deserve 6 pages of code ! Can be done in about 20-25 lines or less than that.

7. @laserlight: Thanks for that algorithm. Looks nice :-)

@ping: I know. As I said, over half of the program length is taken up by visual details. Check the source, or one of my previous posts, for what I mean, because this would be the third time I'd be trying to explain. The program length isn't what bothers me. I know it could be made much shorter. But my question was not "Can this program be made shorter in any way", which is a question all of you, possibly excluding laserlight, are answering to. I don't mean or want to sound ungrateful, but seriously, I don't need to hear that the program could be a thousand times shorter three times for me to acknowledge it. The problem I am having, which was also the reason I started this topic, is stated above, and remains unsolved:

The code works fine, except for one thing, that being that it can't factorize numbers above thirty two thousand something. I can't remember the exact number. I have a feeling that it has something to do with the number of elements an array can have, but I'm not sure. I've tried changing the data type, but even when I use an unsigned long long int it won't change anything.

8. Arrays can certainly go beyond 32767 on a machine with 32-bit registers and sufficient amount of memory to hold the array.

If you are using for example Turbo C, it gives you 16-bit code, so there arrays are limited to 64KB of memory.

You could of course use other techniques to store more than 64KB, but it gets complicated.

--
Mats

9. That was shocking, the formatting that is.

10. Originally Posted by matsp
Arrays can certainly go beyond 32767 on a machine with 32-bit registers and sufficient amount of memory to hold the array.

If you are using for example Turbo C, it gives you 16-bit code, so there arrays are limited to 64KB of memory.

You could of course use other techniques to store more than 64KB, but it gets complicated.

--
Mats

The question immediately arises, how complicated?

11. Instead of using a plain array, you would have to write a function that takes a long int, and then uses multiple tables to look up the value. This simple example shows the principle [but to make it work in a 16-bit environment, you'd have to use dynamic memory allocation to get the data to get over the 64KB limit]:
Code:
```int arr1[100];
int arr2[100];
int arr3[100]
int *arrarr[3] = { arr1, arr2, arr3 };

int findval(int x)
{
return arrarr[x / 100][x % 100];
}```
The overhead of splitting the number and indexing, and calling a function, will be noticable compared to a straight array index.

--
Mats

12. I know. As I said, over half of the program length is taken up by visual details. Check the source, or one of my previous posts, for what I mean, because this would be the third time I'd be trying to explain. The program length isn't what bothers me. I know it could be made much shorter. But my question was not "Can this program be made shorter in any way", which is a question all of you, possibly excluding laserlight, are answering to. I don't mean or want to sound ungrateful, but seriously, I don't need to hear that the program could be a thousand times shorter three times for me to acknowledge it. The problem I am having, which was also the reason I started this topic, is stated above, and remains unsolved:
Smaller code = Easier to Debug.

You do not specify what compiler, what architecture you are working on..

One thing that comes to my mind is your array size which is equal to 2*input. You are declaring it inside main which means on the stack. Make it global.

P.S. I don't feel like going through 6 pages of mindless code when the OP can improve his algorithm as suggested by everyone else and make it easier to debug for all of us.

13. Originally Posted by PING
I don't feel like going through 6 pages of mindless code when the OP can improve his algorithm as suggested by everyone else and make it easier to debug for all of us.
My thoughts exactly. I work as a teaching assistant at my university, and there is nothing more agonizing than a professor asking you to grade a student's 300+ line bloated program that could have been done with around 40-50 lines.

Its much easier to sit down with the student, scrap everything they've written, and explain to them how to do it right (which laserlight helped you with). If you know what you're doing, you should be able to implement the pseudo-code that was posted in less than a half hour, and I think you'll appreciate the elegance of the solution (and how much easier it is to debug!).

As an example of where we're coming from, here's a an actual situation I had to deal with:

A student was asked to write a program that processed a 2D array of numbers. For each number in the array, they needed to check every number around it and do something with it (details not important). One particular student wrote a solution that consisted of a giant if-then-else block that had a separate case for each corner, the top row, the bottom row, the left column, the right column, and every element in the middle. It was HUGE and complicated.

If that student had a tiny bug hidden somewhere in their giant rat's nest of code, do you think I want to wade through all that and find it? Absolutely not. Instead I politely pointed out a much more elegant solution, and once they understood it, I saw that light bulb turn on in their head (one of those 'Ah hah!' moments). They rewrote all their code, and it was MUCH easier to get working.

Originally Posted by Edsger Dijkstra
How do we convince people that in programming simplicity and clarity —in short: what mathematicians call "elegance"— are not a dispensable luxury, but a crucial matter that decides between success and failure?

On a side note, when I'm writing programs, I often realize after I've partially finished that I could have done it so much better a different way. I sometimes rewrite programs SEVERAL TIMES before I'm satisfied. Don't think that this is a sign of a bad programmer. On the contrary I think that makes you a better programmer, and your rewrites will decrease as you gain more experience.
[/edit]

14. I admit, I did get a little impatient. And of course you're right. I apologize. Thanks for the help everyone. I'll have a look at the code, try to re-write it, and then post the final source when I'm done :-) Once more, sorry.

15. That's k, for my first assignment ever, most people did 300 lines of code, i did 1800, lol.

Of course...they were if statements