Algorithms



Hi,
one remark: you should replace the if(){} construct by a while(){} and drop the i;
that way your code is more readable, and you can now more easily reduce the divisor candidates
(say to only 2 and odd numbers, or just primes, or whatever else has already been suggested).





Robert.C.Cartaino wrote: As a college student, you really should be able to do this. It's basic math.
To be fair, my bet is 99% of college students don't know (or care) how to do this, along with 99% of the rest of the world.
I'm about to finish up my second engineering degree, and prime numbers have not been brought up once during the 5 years i've been here.





MarkBrock wrote: my bet is 99% of college students don't know (or care) how to do this, along with 99% of the rest of the world.
I agree. Maybe a bit more than 99%, like 99.9999%
"The clue train passed his station without stopping."  John Simmons / outlaw programmer
"Real programmers just throw a bunch of 1s and 0s at the computer to see what sticks"  Pete O'Hanlon





MarkBrock wrote: To be fair, my bet is 99% of college students don't know (or care) how to do this, along with 99% of the rest of the world.
You must have been taught how at junior school, though
I know, since my son has this in his Math book.





ChandraRam wrote: You must have been taught how at junior school, though
Yeah, I was.
Sit down and watch the TV show "Are you smarter than a 5th grader". Unless you've got better memory than an elephant, I bet you can't answer most of the questions .





You do not need to divide by all numbers, only by primes. If the number is evenly divided by a prime, then keep dividing by that prime until the result leaves a remainder, then go to the next prime. There exists (google primes) a site on which there is a list of the primes for the first million numbers, the second million numbers ... to the first 15 million numbers.
Dave Augustine.





Member 4194593 wrote: You do not need to divide by all numbers, only by primes.
... and, if we are optimizing, your forloop does not need to run all the way up to InputCase . You only need to check for divisibility of numbers up to the square root of InputCase .





I see. I'll apply both suggestions.
That's why its so slow at 20!.
It is said that the most complex structures built by mankind are software systems. This is not generally appreciated because most people cannot see them. Maybe that's a good thing because if we saw them as buildings, we'd deem many of them unsafe.





Ian Uy wrote: That's why its so slow at 20!.
There are easier ways of factorizing 20!
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."





A possible solution would be as follows:
void prime_factors(unsigned int n, std::deque<std::pair<unsigned int,unsigned int>>& factor_list)
{
factor_list.clear();
unsigned int upper_bound = ::floor(std::sqrt(n));
unsigned int i = 2;
while(i <= upper_bound)
{
std::pair<unsigned int, unsigned int> current_factor(i,0);
while(0 == (n % i))
{
n /= i;
++current_factor.second;
}
if (current_factor.second > 0)
{
factor_list.push_back(current_factor);
}
++i;
}
}
The primefactors will be in the deque, the first of each element is the factor and the second is the recurrence count of the factor.
[updated]







General News Suggestion Question Bug Answer Joke Praise Rant Admin
Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.