Project Euler #3 Solution Crashing

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?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <math.h>
#include <iostream>
using namespace 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
	long long check = 600851475143L; //for use in the do while loop
	long double 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;
}
Division by zero is not allowed.
where is there division by zero?
Line 28 will break out of the loop long before value ever hits 0
I think he's talking about line 11 where you use value % i when i is initialized to 0.
Thanks, But i'm still having a problem, I changed it to count up and just list off the primes.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <math.h>
#include <iostream>
using namespace 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
	long long check = 600851475143L;
	long double 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?
Last edited on
Your isPrime function is exiting after the first test because of a lack of brackets.

This:
1
2
3
if(value % i == 0)
     isPrimeR = false;
     break;//goto return the false bool 


Should be this:
1
2
3
4
if(value % i == 0) {
     isPrimeR = false;
     break;//goto return the false bool
}
Huh, thanks, I didn't know it worked like that.
Check out this link for a good explanation of control structures, and the use of { } brackets: http://www.cplusplus.com/doc/tutorial/control/
thanks!
Topic archived. No new replies allowed.