Tomer Daloomi Tomer Daloomi - 3 months ago 10
C++ Question

difficulty with prob.3 on project euler (in c++)

so, I've been trying to solve this problem for a few hours now.
shortly I arrived to a solution that logically - should work and is working, but only for numbers no bigger than 10^7. I guess I could just const the specific number they asked for (600851475143) but I would really love to know - why my code isn't working with big numbers?

this is my code for the solution :

#include <iostream>
#include <stdlib.h>
#include <cmath>

using namespace std;
//enter any number and its largest prime factor will be detected.
int main()
{
long largest(1),num(0);
bool primecheck;
cout<<"enter the desired number :"<<endl;
cin>>num;
if (num%2==0)
largest=2;
cout<<"the relevant factors are: ";
for (int i=3;i<=int((sqrt(num))/2);i+=2)
{
primecheck=true;
for(int j=2;j<i;j++)
{
if(i%j==0)
primecheck=false;
}
if(primecheck)
if(num%i==0)
{
largest=i;
cout<< largest<<"\t";
}
}
cout<<endl<< "the largest prime factor of the number you have entered is: " <<largest;
return 0;
}


thanks in advance! :)

Answer

Problem with your code-

Use long long int as data type instead of long int since C++ recognizes long int as having same range as int.

If you want to refer my concise solution in C/C++ -

*For C++ just change the header file to iostream.

#include <cstdio>
#define MAX 775147
#define NUM 600851475143

int main()
{
  long long n = NUM;
  int max = 3;
  for(int i = 3; i <= MAX; i+=2)
  {
    if(n%i == 0)
      max = i;
    while(n%i == 0)
    {
      n /= i; 
    }
  }
  printf("%d\n", max);
  return 0;  
}