# Thread: Largest prime factor...

1. ## Largest prime factor...

I am trying to solve some problems on Project Euler, and currently have very little experience with or knowledge about programming. I've learned up until while loops :P
Anyways, I decided to see how many I can do before I have to move on and continue learning. This problem was the one I decided to stop after, as it took me a while to figure out:
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?

The problem here is that while writing the code, I had x variable assigned to 13195, so that I would know if it is working correctly depending on whether or not it displayed 29. Now, I am faced with the problem of 600851475143 being too large for an int variable. As a matter of fact, it's even too long for a long long int variable.
However, I am somewhat opposed to the idea of just having someone do all the work for me (but honestly, I'm happy I made it this far with what little knowledge I have), so if upon reviewing the code you notice that I won't be able to actually make this code work without making drastic changes, than please tell me so and I will just leave this until later. Otherwise, I'm all ears
*Please note another flaw, 2 is never considered as a prime number when you run this, but I ignored that for now because there will of course in this case be larger prime factors, so the answer should still be correct*

Code:
```#include <stdio.h>
int main(void)
{
int count = 2, countdiv = 2, x = 13195, div = 0, prime = 0; //count is to count till x (to find the factors), countdiv is to count till count (while checking if prime), div = divisor
while(count < x) // This outer while loop is meant to find the factors of x
{
if (x % count == 0) // This actually checks if the counter is indeed a factor of x
{
div = count; // div (for divisor) is now the value of whichever integer is being checked
countdiv = 2; // This is required, as you'll see further down to end the while loop I had to assign countdiv a higher value than div, and this resets it so that it can be used in following loops
while(countdiv <= div) // *Check after code for info
{
if(div % countdiv != 0){ // If it is a prime number SO FAR...
countdiv++;} // Check the next counter (ex : 5 % 2, prime so far, check 5 % 3, 5 % 4)
else{
countdiv += div;} // If it is NOT a prime number, than end the loop (make countdiv larger than div) and check the next factors

if(countdiv == div){ // If countdiv reaches the value of div, then the loop has not been ended, meaning div IS prime
prime = div; // Hmm, I wonder what this does?
printf("Prime: %d\n", prime);
}
}
count++; // Adds 1 to count if it is a factor of x, so that more prime factors can be found
}
else
count++; // Adds 1 to count if it is NOT a factor of x, so that a factor CAN be found
}
printf("The largest prime factor of %d is:\n>%d\n", x, prime); // Outputs answer
return 0;
}```
Thanks in advance for any help!

2. You either need to use a library that handles exceptionally large numbers, or you need to do all the conversion back and forth yourself using strings.

Quzah.

3. P.S - When I add long long to the start of the int line, and then run it, the output is:
Prime: 71
Prime: 839
Prime: 1471
Prime: 6857
and then it just hangs there and does nothing

4. It's probably not that it's hanging. It's probably working on whatever the next number is. Add in some printf statements if you want to know for sure.

Quzah.

5. Originally Posted by quzah
You either need to use a library that handles exceptionally large numbers, or you need to do all the conversion back and forth yourself using strings.
Ahh, yes someone mentioned using a library to me. I'm not sure what you mean by doing the conversion between strings (as in character strings?), so I'll assume that it's too advanced for me at this point. However, do you know where I could find out what library to include (if I have to download it, maybe you could tell me where to find it?)

6. 1. Find a search engine.
2. Type these magic words: c large number library
3. Locate the button labeled "Magic".
4. Press it.

Quzah.

7. Originally Posted by quzah
It's probably not that it's hanging. It's probably working on whatever the next number is. Add in some printf statements if you want to know for sure.

Quzah.
I think you are right, added in a few printf's saying "About to check if this is a factor" and "about to check if factor is prime", and now it's just a blinking wall of text ^.^ Thanks for that, had I not known I wouldn't have thought to leave it open for so long. Now I know what to do when dealing with large numbers in the future. Cheers, and thanks for the incredibly quick replies btw.

8. You'll probably want to go ahead and take them back out now that you know it's not broken. It is going to slow it down a huge amount writing all of that over and over.

Quzah.

9. Originally Posted by quzah
You'll probably want to go ahead and take them back out now that you know it's not broken. It is going to slow it down a huge amount writing all of that over and over.

Quzah.
Yes, I took out the ones that say "About to check if factor", and it's going much faster. I'll take out the other one as well though, I didn't realize they could slow it down so much. Thanks again

Originally Posted by quzah
1. Find a search engine.
2. Type these magic words: c large number library
3. Locate the button labeled "Magic".
4. Press it.

Quzah.
I can't see any "Magic" button???

Popular pages Recent additions