Euler Project Problem #3

[GoranGaming]

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?

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

int main(){
    double z = 600851475143, greatprime = 0;
    for(double x = 2; x < z; x++){
        if(fmod(z,x) == 0){
            greatprime = x;
        }
    }
    cout << greatprime;
}

[Manga]

set double x to 1 instead of 2 and see what happens.
nope I think I see it. try

double z = 600851475143;
double greatprime = 0;

greatprime might not be a double.

Im new at this.

[Ispil]

...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.

[GoranGaming]

I tried it, but the program still does not output anything. Not even the usual lines of code it always runs in the end (of my programs):

"Process returned 0 (0x0) execution time : bla bla
Press any key to continue."

[cire]

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.

[Ispil]

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.

That is going to take a while.

[GoranGaming]

Don't blame me, I'm a beginner at this :) Oh... I guess that was why nothing happened xD Thank you everyone

[giblit]

Ispil wrote:

Also, there's no need to go up to more than half of z- everything past that will not divide in by definition.

To check if a number is prime you would have to see if any of the numbers from 2 -> sqrt( n ) or n^.5 as far as I am aware http://www.wikihow.com/Check-if-a-Number-Is-Prime

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.

[Ispil]

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.

[naraku9333]

Actually there is no reason to get fancy with this one, checking to sqrt(n) will be fine.

[Manga]

int main() {
	
	long int x;
	x = 0;
	while(x<=0) {
		cout << "Enter an integer greater than 0." << endl;
	  cin >> x;
	}
	int count = 0;
	int temp = 0;
	int largestprime = 0;
	for(int i=(x/2); i>0; i--){
		if(x % i== 0) {
			//cout << i << ": a multiple of x" << endl;
			count = 0;
			for(int j=(i/2); j>0; j--){
				if(i % j== 0) {
		          //cout << j << ": a multiple of i" << endl;
		          count++;
				}
			}
			if(count == 1 && largestprime == 0) largestprime= i;
		}
	}
	if (largestprime != 0) {
	cout << largestprime << " is the largest prime multiple of " << x << endl;;
	}
	else {
		cout << x << " is a prime number." << endl;
	}

	system("PAUSE");
	return 0;
}

this one you can pick a number. then it counts down for multiples of your pick. the first prime occurance is the one it displays.

[GoranGaming]

Thanks, but I do not really understand that code.

[Manga]

I'm still new at this myself. that is why it looks sloppy.

which line do you have trouble with?

EDIT:

I tried the number you supplied at first. 600851475143
this crashed my program.
apparently I needed a "long long int" to make it work.

I think though it is a trick problem because I show 600851475143 as being a prime number itself. Did anyone else get the same results?

[cire]

giblit wrote:

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.

[ne555]

There shouldn't be a problem if it were prime.

[gobiking]

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>

using namespace std;

int main()
{
	unsigned long long int num;
	int divisor;
	unsigned long long int 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 (unsigned long long int 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);
}

[18hRX9L8]

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:

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 

Returns: [71, 839, 1471, 6857]

[Chervil]

The Python code looks useful. However, I'd suggest that false=True shows an unfortunate choice of variable name.

[Manga]

I see my mystake!

all int variables should be of long long type.

if you go into my "for" loops and change the int to long long int it works!

but it is such a big number it takes for ever to run. what a challenge!
thanks gorangaming, this has been fun.

[Chervil]

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.