C++ Prime Number Program Issue

[Gaving30]

Hi All,
First time asking so go easy :-)

I am doing c++ a few weeks now, i am doing questions in Project Euler to hopefully improve my coding, But as you will prob see below i am still very new and "Nieve"...

Question is: The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143?

My Issue: I am trying to get 5 as the first prime number by putting this in (if((digit > 5) && (digit%5) !=0)) but its not working, can anyone assist or am i maybe writing this whole code the wrong way as in should i use different methode/ loops etc?

Below is my code so far:

#include <iostream>
 using namespace std;
 
void main(){
 long long int number = 600851475143;
 long long int biggestPrime = 1;
 

for(long long int digit = 1; digit<=number; ++digit){
 if((digit%2) !=0 && (digit%3) !=0){
 if((digit > 5) && (digit%5) !=0){
 if((number%digit) == 0){
 if(digit > biggestPrime){
 biggestPrime = digit;
 cout << digit << endl;
 }
 }
 }
 }
 }
 cout << "Finished";
 int dummy; cin >> dummy;
 }

Any assistance would be greatly appreciated.....

[nmaillet]

That statement will not return true for 5, for two reasons. digit would not be greater than 5, it would be equal, and 5 mod 5 equals 0. Both would be false.

I don't really understand why you are performing the checks:

if((digit%2) !=0 && (digit%3) !=0){
if((digit > 5) && (digit%5) !=0){

You should first be checking if number is divisible by digit (ie. number % digit == 0 ). Then you should add in a for loop to determine if the digit is prime; probably as another function for simplicity's sake.

Since Project Euler is generally about efficiency, I should mention that:
a) you don't need to check if(digit > biggestPrime) since i is always increasing, each time it will be greater than the last.
b) since even numbers (except 2 of course) are never prime, you do not have to check them, and there will never be a factor greater than the number divided by 2 (unless the number itself is prime). You could reduce your for-loop to:

long long int halfNumber = number / 2;
for(long long int digit = 3; digit <= halfNumber; digit += 2)

P.S. Please preview your post before submitting, or edit it right afterwards. It is much easier to read code if the CODE tags are used properly.

[TrustyTony]

I would say that biggest possible factor is third or 7th of the non-prime odd number not ending with 5.

[Cross213]

The word is naive

[Caligulaminus]

And I thought it was naïve. :icon_mrgreen:

[Gaving30]

//The prime factors of 13195 are 5, 7, 13 and 29.
//What is the largest prime factor of the number 600851475143 ?

#include <iostream>
using namespace std;

void main(){
	long long int number = 600851475143;
	long long int halfNumber = number/2;	//as 600851475143 isnt a prime number this will work
	long long int sum = 1;

	for(long long int digit = 3; digit <= halfNumber; digit += 2)
		if(number%digit == 0){
			sum*=digit;
			if(sum == number){
				cout << digit << " = " << sum << endl;
				break;
			}
			cout << digit << " x ";
		}
		cout << "So the highest prime Factor is 6857";
		int dummy; cin >> dummy;
}

Hi all, thanks for help with this, just taught i would put up my final program, spent my weekend staring blankly at this until the penny dropped :-)
Cheers nmaillet ;-) appreciate the help......

[TrustyTony]

I do not think your solution would work in general case, as there is not while loop for factors appearing more than once. Also you have main still as void. Here my alternative:

//The prime factors of 13195 are 5, 7, 13 and 29.
//What is the largest prime factor of the number 600851475143 ?

#include <iostream>
#include <stdlib.h>
using namespace std;

int main(){
	long long int number = 600851475143;
	// digit += 2 => square += 4 * (digit + 1)
	for(long long int digit = 3, limit = digit * digit; number > limit ; limit += 4 * (digit + 1), digit += 2)
		while(number % digit == 0){
			number /= digit;
		}
    cout << "Biggest factor is " << number <<".\n";
    return EXIT_SUCCESS;
}

[TrustyTony]

I believe it should also be long long (without int) for minimum 64 bit int.

//The prime factors of 13195 are 5, 7, 13 and 29.
//What is the largest prime factor of the number 600851475143 ?

#include <iostream>
#include <stdlib.h>
using namespace std;

int main(){
	long long number = 600851475143*6857; // check the case multiple times the biggest factor
	// factor += 2 => square += 4 * (factor + 1)
	for(long long factor = 3, limit = factor * factor; number >= limit ; limit += 4 * (factor + 1), factor += 2) {
		while((number > factor) && (number % factor == 0)){
	                cout << factor << " * ";
			number /= factor;
		}
    }

    cout << number << endl << "Biggest factor is " << number <<".\n";
    return EXIT_SUCCESS;
}