This is the problem from projecteuler.net (it's one of the first ones)
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
I thought I would simply create an isPrime() function to test if a factor that I would find in main() was prime, and if it was, exit. Since I am looking for the largest prime factor I should start at the top of the possible candidates and work my way down so I know the first one I get to is it.
My code compiles, but the output from the build crashes without ever printing. What am I doing wrong?
#include <math.h>
#include <iostream>
usingnamespace std;
bool isPrime(long value)
{
bool isPrimeR(true);
int tip = (int)(value/2); //test to this value for factors
for(int i(0); i <= tip; i++) {//returns positive if we reach tip
if(value % i == 0) //if we find a factor
isPrimeR = false; //it's not prime
break;//goto return the false bool
}
return isPrimeR;
}
int main()
{
long value; //for use in the do while loop
longlong check = 600851475143L; //for use in the do while loop
longdouble valueLD = (sqrt(600851475143.0)); // find the starting point
value = (long)(valueLD); //convert to long
do {
value--; //subtract 1 from value
if(check % value != 0) // test if it is not a factor
continue; //if not, don't check to see if it's prime
} while (isPrime(value) == false); //if it is a factor, check isPrime
cout << value; //print the first prime factor you get
return 0;
}
#include <math.h>
#include <iostream>
usingnamespace std;
bool isPrime(long value)
{
bool isPrimeR(true);
int tip = (int)(value/2); //test to this value for factors
for(int i(2); i <= tip; i++) {//returns positive if we reach tip
if(value % i == 0) //if we find a factor
isPrimeR = false; //it's not prime
break;//goto return the false bool
}
return isPrimeR;
}
int main()
{
int dummy(0);
long value; //for use in the do while loop
longlong check = 600851475143L;
longdouble valueLD = (sqrt(600851475143.0)); // find the starting point
value = (long)(valueLD); //convert to long
for(int i(1); i <= value; i++) {
if(check % i == 0)
if(isPrime(i) == 1)
cout << i << endl;
}
cin >> value;
return 0;
}
it gives me the values
and it says these are all prime factors
1
71
839
1471
6857
59569
104441
486847
so the answer should be 486847, but the site says it's actually 6857. Why does my program return the larger numbers as prime factors if they are wrong? It seems like it's just spitting out the factors and isPrime() isn't working.
Can you please point out what is wrong in my isPrime() function?