prime factorization

Okay, so I've decided to start learning some C++ on my own, well sort of. I'm running xCode 4 on my Mac and I decided to start learning some C++ by going through Project Euler and struggling, but learning a lot along the way. I got through the first 2 relatively easily, but this third one has me stumped. The problem is that it wants to find the greatest prime factor for 600851475143. I've tried a few different codes and the one I currently have is working for me for relatively small numbers, but once I test it out with this huge number, it just keeps saying "running..." but doesn't return a value. My assumption is that the algorithm I currently have is functional, but is much too lengthy for a number of that magnitude. This is the code that I currently have. Any help at all would be appreciated. Thanks.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
using namespace std;
int main()
{
    long long int Prime=0, i, F=0;
    cout << "Please enter number: ";
    cin >> Prime;
    for (i = Prime/2; i >2; --i)
    {
            if (Prime%i == 0)
                F = i;
        
        }
    cout << "The greatest prime factor is " << F << ".";

    return 0;
}
There's a bug, it includes compound number 4 as a result on other numbers. IDK about how to fix it. How about unsigned long long long long long int? Might just work
You aren't testing for prime factors. You're testing for factors.
Well, my thought process was that if I keep dividing the number, it will eventually become prime itself, and that would be its greatest prime factor. I guess I just haven't been able to make sure that F is a prime number. Would I need to include more nested for if loops to ensure that it's a prime number? I just don't know where to go from here.
Well, my thought process was that if I keep dividing the number, it will eventually become prime itself, and that would be its greatest prime factor.


It's a good thought, but you aren't modifying Prime, so it will never become anything but itself. Also, a for loop wouldn't be appropriate for that process. If a number is evenly divisible by 2, the quotient may also be divisible by 2, suggesting that i should not be modified every iteration of the loop.
Well, that's true. Maybe my approach isn't the best. Any ideas for how to do this, then? I thought of possibly having a do while loop, but I can't figure out a way to implement it in a way that it would be more useful than having for if loops.
Sometimes it helps to work out how it would work if you were doing it on paper before translating your thoughts into code, particularly when you're new to the process of coding.

Here's some pseudo code for the process you described:

1
2
3
4
5
6
7
8
9
10
11
12
num_type largestPrimeFactor(num_type number)
    divisor = 2
    while divisor is less than number
        while number is evenly divisble by divisor
            set number to quotient of number and divisor
        end while

        increment divisor
    end while

    return number
end largestPrimeFactor
Topic archived. No new replies allowed.