Hello!
I've been trying to solve problem number 3 of the "Euler Project", which basically is to find the largest prime factor of 600851475143, but my code does not seem to be working. The program just runs, but nothing gets written at all, and it gives me no errors. If you could help me with solving this problem, and tell me what was wrong with my code, I would be very grateful :) EDIT: Maybe I've let the computer run through too many numbers, and that is why it does not write anything?
1 2 3 4 5 6 7 8 9 10 11 12 13
#include <iostream>
#include <math.h>
usingnamespace std;
int main(){
double z = 600851475143, greatprime = 0;
for(double x = 2; x < z; x++){
if(fmod(z,x) == 0){
greatprime = x;
}
}
cout << greatprime;
}
...why are you even using type double? It's completely unnecessary. Also, your program does not write anything because it is going to take a very long time to reach 600 billion. Try creating a list of primes as you go, then not check any number that isn't prime in itself. Also, there's no need to go up to more than half of z- everything past that will not divide in by definition.
As has been indicated, your algorithm is going to take a very long time to complete. And besides that -- it's wrong. It will find the largest factor. It will not find the largest prime factor.
Also, because your program isn't actually checking if the number is prime, you've created a simple counter, with a few unnecessary steps in-between counting. In short, your computer is trying to count to 600 billion.
Also like the others said you are just checking the factors not the primes.
I actually was working on this problem earlier but it was taking too long what I am going to do is output the primes to a txt file and run it a few times and then read in that file each time till I eventually have all the primes that are less than 600Billion and then check all those numbers and see if they are factors instead of getting all the factors of 600 billion ( which is far greater ) then seeing which ones are primes. I tried that earlier and waited about an hour and still got no results but I am going on a work trip this week so won't be able to finish for a while =/ only had about 20 minutes to work on it. That website is a pretty neat site though.
Well, there's an issue with that as well- there are a lot of primes between 1 and 600 billion, so it will still not complete in any decent time. What you need to do is figure out a way to calculate primes much faster... Remember, you don't need every prime. Only the largest that evenly divides into 600 billion.
To check if a number is prime you would have to see if any of the numbers
This one can be solved without ever explicitly checking a number for primality, although it does require understanding what primes are and how numbers are factored. If you factor a number by hand and look closely, I think the algorithm becomes fairly obvious.
For instance to factor the value 819:
819
/\
3 273
/\
3 91
/\
7 13
The prime factors are 3, 7 and 13.
Manga wrote:
I think though it is a trick problem because I show 600851475143 as being a prime number itself.
It is not a trick question. 600851475143 is not prime.
Yeah... I went a little crazy with the brackets XD was getting a little lost with my loops. But this lets you find the greatest prime factor of any value up to whatever the limit of unsigned long long is. Im still new to programming so it's probably very crude =X
#include <cmath>
#include <iostream>
usingnamespace std;
int main()
{
unsignedlonglongint num;
int divisor;
unsignedlonglongint gpf=1;//just setting up a dummy value
cin>>num; //number you want to find prime of
cin>>divisor; //number you want to use as divisor
do
{
if(num%divisor==0) //will keep dividing as long as divisor divides into num evenly
{
num/=divisor;
}
else
{ for (unsignedlonglongint i=2; i<=num ; i++)//will try all values to see if number prime.
{
num%i;
if (i==num) //will set as gpf if you reach num also must be first on list cause otherwise num%i will = 0
{
gpf=num;
cout<<"The greatest prime factor is "<<gpf<<endl;
break;
}
if(num%i==0) //found a factor of number
{
cout<<"("<<i<<" was the factor)"<<endl;
num/=i;
break;
}
}
}
}while (gpf!=num);
}
Okay, I know this is a C++ forum, but this algorithm might come to use. I don't know if you have Python or not, but Python is easy to use because you don't have to worry about calling memory-specific objects (like int,bool,double,etc...(but eventually, we will get a Memory Error if we put in big enough numbers. This is one known problem with using this kind of language.)). So, anyway, running this Python code:
1 2 3 4 5 6 7 8 9 10
def findprime(pnum,li=[1]): // defining a function called findprime that takes in a number and a list (in this case like an array) as arguments
compo=False // in Python, we just define an object by putting it into the script. Also, False=FALSE
for x in range(2,int(pnum**0.5)+1): // this is like a for((?int?) x=2;x<(int)sqrt(pnum)+1;x++) { ... }
if(pnum%x==0): // we check is pnum can be divided
findprime(x,li) // if it can, then find primes of x
compo=True // and that means pnum is composite, so don't add it to the list
if(compo==False): // if pnum is prime, add it to the list
if(not(pnum in li)): // check is pnum is already in the list
li.append(pnum) // otherwise, add pnum to the list
return li // at the end of the program, return the complete list of prime factors
but it is such a big number it takes for ever to run
A lot of the Euler challenges are like this. It's usually not enough to have some code which works and gives the correct results. It's also important to think of how to design a solution which runs quickly and efficiently.