C++ Prime Factor Program

[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;
}

[xibz]

I have no idea what your trying to do, but I would suggest writing a isprime function and writing a factor_out function. The factor_out function would need to be called recursively until isprime returns true and return the tested value.

factor_out needs to be called when it finds the first number that can divide 600851475143 evenly. Than factor_out is called

[tition]

[Spoiler]The answer you should get is [Spoiler ahead]:



































_{600851475143= 71* 839*1471*6857}[/Spoiler]

[kalgorithmist]

:D I know that problem on project Euler.

Try to use the Sieve of Eratosthenes algorithm; for the sake of time saving and precision.

Google it :-)

[xibz]

I think the Sieve of Eratosthenes algorithm may be slower in this case. Because you simply have to find out if a factor is prime, not all prime numbers up to N.

I wrote my code without using it, and it ran in less than a second. It's a pretty simple problem, so I don't think it would take that much time.

[TheMassiveChipmunk]

http://en.wikipedia.org/wiki/Fermat's_little_theorem
Fermat's algorithm is good too.

[Gaving30]

Thanks for the help and replies, i now have this code doing as i need to do:

//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;
}