|
Ian Uy wrote: I'm lost on how to begin to tackle this problem. Please advice.
As a college student, you really should be able to do this. It's basic math.
What you will want to search for is called "prime factorization." The easiest-to-understand technique is called "trial division."
On paper, you start by writing down your large number (let's call it 'n'). Then try to think of another number which divides evenly into n without any remainder. That number is a factor of n. It's easiest to start with small numbers.
In your example, what number divides evenly into 120? How about 2? Yes, 120/2=60. So write down 2 and 60 (those are factors of 120, but not necessarily prime).
Then try to factor each number you wrote down (the 2 and the 60). Are there any numbers (other than 1) that divide into 2 evenly? No, so 2 is a "prime factor" of 120 (i.e. 2 cannot be divided any further).
How about the 60? 60/2=30. So, there is another 2 that is a prime factor of 120. So far we have the factors of 120=2,2,30. Now factor the 30 and keep going.
Keep going until you run out of numbers that can be divided evenly. Those will be your prime factors.
120 factored = 2,60 (2 is prime)
60 factored = 2,30 (2 is prime)
30 factored = 2,15 (2 is prime)
15 factored = 3,5 (both 3 and 5 are prime)
Done.
The prime factors of 120 are (from the parentheses above) 2,2,2,3,5.
Now try writing that in code and see what you come up with. You can use this Table of Prime Factors[^] to check your answers.
|
|
|
|
|
Thank you. I have always been really stupid in basic math.
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: I have always been really stupid in basic math.
If you are stupid in math i strongly advice you to change you major because math is core for Computer sceince.
The Developer - CEH
|
|
|
|
|
Thanks for your reply. I have successfully translated it into C++.
int main()
{
int InputCase;
cin >> InputCase;
for(int i=2;i<=InputCase;i++)
{
if(InputCase%i==0)
{
cout << i;
InputCase/=i;
i--;
}
}
return 0;
}
Thanks! 
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.
|
|
|
|
|
Are you sure this works? There are cases where i is not a prime...
"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
|
|
|
|
|
Yup, for some reason it did threw the right answers.
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.
|
|
|
|
|
That is interesting.
"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
|
|
|
|
|
It works, but it's inefficient.
/ravi
|
|
|
|
|
Ian Uy wrote: Yup, for some reason it did threw the right answers.
I think if you're aiming for the ACM ICPC then you should try to understand why it gives the correct answers (and at first glance it looks as if it should). The fact that i may not be prime actually doesn't matter (well except for efficiency concerns).
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."
|
|
|
|
|
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 for-loop 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 prime-factors will be in the deque, the first of each element is the factor and the second is the recurrence count of the factor.
[updated]
|
|
|
|
|
[edit] since Arash has completely changed the code in his previous post, this appears somewhat out of context [/edit]
I think this is an example of misguided optimization. Whilst Ian Uy's example looks inefficient
int main()
{
int InputCase;
cin >> InputCase;
for(int i=2;i<=InputCase;i++)
{
if(InputCase%i==0)
{
cout << i;
InputCase/=i;
i--;
}
}
return 0;
}
all he is doing each iteration is testing
if(InputCase%i==0)
In order to avoid these "unnecessary" tests, you are testing each n as
if (n % 2 == 0) n++;
while(!is_prime(n)) { ++n; }
The function is_prime(n) will involve much more overhead than the original code, and it doesn't matter that 'i' may not be prime.
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."
modified on Saturday, October 18, 2008 11:35 PM
|
|
|
|
|
Hi Peter,
I agree.
Some improvements are possible, but they do not involve adding method calls:
1. replacing if(){} by while(){} and dropping the i--;
then changing the for loop so it starts with 3 and increments by 2 or by 2 and 4 alternating
(make sure to test 2 itself also)
2. use multiple (say two) threads, assuming a Core Duo or something similar.
|
|
|
|
|
Hi Luc,
True. The most important thing he should do is limit the testing to sqrt(N).
To factorise a number N, you need to test up to sqrt(N), and there are approximately
sqrt(N)/log(sqrt(N)) primes to test. For example, to factorise 1,000,000 you only need to test the 168 primes less than 1000, or 16.8% of the numbers less than 1000.
Using the simple algorithm you test 100% of the numbers less than sqrt(N):
if you eliminate the multiples of 2 you are down to testing about 50%
then eliminating the multiples of 3 drops you to testing 33.3%
then eliminating the multiples of 5 drops you to testing 26.7%
and so on.
the first few are probably worthwhile as you point out, but you then rapidly get in to diminishing returns, and may easily get to the stage where it is not worth the effort to save the time of the line
if(InputCase%i==0)
I don't think multiple threads are worthwhile until you go past 32 bit arithmetic (even the simplest algorithm only has 2^16 tests to do).
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."
modified on Sunday, June 29, 2008 10:10 PM
|
|
|
|
|
cp9876 wrote: The most important thing he should do is limit the testing to sqrt(N).
I believe this is not correct, assume you have an x composed from 2p where p is a prime, in this case it is clear that in certain circumstance sqrt(x) can be less than p (eg: 15838 = 7919 * 2, where 7919 > sqrt(15838)), for primal testing the sqrt(n) bound is ok, however its not suitable for the upper bound in this problem.
|
|
|
|
|
Arash Partow wrote: I believe this is not correct, assume you have an x composed from 2p where p is a prime, in this case it is clear that in certain circumstance sqrt(x) can be less than p (eg: 15838 = 7919 * 2, where 7919 > sqrt(15838)), for primal testing the sqrt(n) bound is ok, however its not suitable for the upper bound in this problem.
He's studying for the ACM competition - I don't want to spoon feed him! He can limit his testing to sqrt(N) but he has to modify his algorithm slightly for when InputCase is not 1 at the end.
In the example you give, he only needs to test until floor(sqrt(15838))=125, he will have only found 2 as a factor and InputCase will be 7919 after the 124 tests. He can then conclude the the remaining value in InputCase is the remaining prime factor. This is much more efficient than testing the remaining 15,703 factors.
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."
|
|
|
|
|
cp9876 wrote: This is much more efficient than testing the remaining 15,703 factors.
true.
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
