This discussion has been moved from http://www.daniweb.com/forums/thread284115.html. Check there for the beginning.
= = = = = = = = = = = = = = = = = = = =
Actually neither approach is wrong.
The original code does not store prime numbers but does correctly identify all prime numbers although it does test some values such as 9 that are not required.
The approach suggested by 0x69 requires that you have already found all the prime numbers <= sqrt(userInput). This value is limited by the sizeof int so it is feasible to store all the require prime numbers in an array to facilitate factorisation.
The original code uses less memory but takes more processing (because it tests numbers that are not prime so can be part of the result), 0x69 solution takes less processing but takes more memory (on a 32 bit system enough to hold about 726800 prime numbers) because you have to store that table of prime factors.
So its a trade off, do you want to use an algorithm that uses less processing or one that uses less memory. And you can only really answer that question once you have decided what platform you will be running on and the limits of the algorithm you are writing (perhaps you only need to factorise numbers up to 500, that would reduce the memory requirement quite a bit).
However as I originally said neither algorithm is wrong it depends on circumstances.
Edited 6 Years Ago by WaltP: n/a