Prime factor of 600851475143

[persontothe]

Hi, I'm working on a problem for project Euler and its asking me to get the greatest prime factor of 600851475143. I made the code that would give me it but after a certain number :716151937. It stops computing. If someone could point me in the right direction that would be great.

#include <iostream>

using namespace std;


  
      int IsPrime(long long num) // 1 == prime and 0 == not prime
{
        int ans=1;

	for(int i = 2; i <= num/2; i++)
	{
		if(num % i == 0)
               {
			ans = 0;
                        break;
               }	
	}

        return ans;
}


int main ()

{ long long int c = 2;
 long long int num = 600851475143LL ;
  long long int lf;
  long long int rr;
  long long int cc;
  for (c = 2; c < 300425737572LL ; c++)
 { rr = num % c;
 if (rr == 0)
{  cc = IsPrime(c); 
  if(cc == 1) lf = c; cout << "||" <<c << "||"; }
  
}

cout << lf << "end";
  system("PAUSE");
  
  
  
  
  
  
     } 

[cire]

I don't think it stops. I think your algorithm is just going to take a very long time to finish.

Also, it might make more sense if you were to only output numbers for which isPrime returned true. Your rather horrible indentation and formatting probably lead to you think that's what you're doing now, but you are not.

You may also want to consider this:

If I wanted to find the greatest prime factor for 78 and I did it on paper, I might come up with something that looks like:

    78
    |
  2 * 39
      |
    3 * 13

which may be suggestive to you. Once you've found a factor, the number you're trying to factor can be reduced. The largest prime factor of 78 is the largest prime factor of 39 which is also the largest prime factor of 13, which happens to be prime.

[SamuelAdams]

Confirmed what cire said, modified your main and after a few seconds it shows that it's still working.

int main ()
{
	long long int c = 2;
	long long int num = 600851475143LL;
	long long int lf;
	long long int rr;
	long long int cc;
	for (c = 2; c < 300425737572LL; c++)
	{
if (c>=716151937)
{cout << c << endl;}
	rr = num % c;
	if (rr == 0)
		{  cc = IsPrime(c); 
			if(cc == 1) lf = c; cout << "||" <<c << "||"; }
		}
	
	cout << lf << "end";
}