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

I came up with the following code. This did compile in VC++ Express Edition without any errors/warnings. But i only get a blank output screen. Someone plz point out where i went wrong?

#include <iostream>
#include <vector>

using namespace std;

class factor
		/*_int64*/ long long target;
		vector<long long> pno; 
		vector<long long> ::iterator it; 

		void prime();

void factor::prime()
	target = 600851475143;
	int flag = 0;
	pno.push_back(7); // Pushing prime no s within 10 into the vector
	for (long long i = 11; i<target; i++)
			pno.push_back(i); // Checking if the no has factors other than itself and 1, then pushing it into the vector. 

	cout << "Prime No" << endl << endl;
	for (it = pno.begin(); it != pno.end(); it++)
		cout << *it << "\t";
	cout << endl << endl;  // Printing the vector for reference

	for (int j = (pno.size()-1); j>0; j--)
			cout << "Largest prime factor of the no '600851475143' : " << pno[j] << endl << endl;
	} // Checking the vector of prime no s if it a factor of the target no. Since we are traversing the vector back to front, the first factor we find is the largest prime factor of the target no. 

int main()
	factor inst;

Recommended Answers

All 2 Replies

Sorry I am going to be harsh. This is by far and away the worst prime factor sort that I have EVER EVER seen. Do not code until you have considered the maths.

Consider a number[TEX] N[/TEX]. (which is a positive integer)
First if a number has a prime factor, [TEX]p[/TEX], e.g 2,3 etc. The biggest prime factor is either [TEX]p[/TEX] or the biggest prime factor of [TEX]N/p[/TEX].

That allows you to reduce the number you are searching for by a long way.

Second, from the first rule you can deduce that the largest value you need to test is the [TEX]\sqrt{N}[/TEX] [rounded down to the nearest integer]
Pseudo Proof :
consider two prime factors: [TEX]a,b[/TEX] such that [TEX]ab=N[/TEX], then if [TEX]a=N^{1/2}+x[/TEX] and [TEX]b=N^{1/2}+y[/TEX] obviously [TEX]ab=N+xy+(x+y)N^{1/2}[/TEX].

[Note [TEX]x^{1/2}[/TEX] is the same as[TEX] sqrt{x}[/TEX] ]

So why does your problem return a blank screen --- because it is using billions and billions of CPU cycles and expanding a vector to an unbelievable size.

Finally?: Your code doesn't even give the right answer! Try 121 as the input value.

Finding prime factors from large numbers is an extremely difficult thing to do. (and extremely CPU + memory intensive). But there is a lot of literature on this, and a lot of improvements over Eratosthene's sieve method, but to make it an O(N) worst is impressive :)

How to proceed

So I would start with a simple routine to check if a number is prime.
Use Eratosthene's sieve method. Limit the check to sqrt(N). Don't try to be fancy.

Next generate a list of prime numbers below 100, then below 1000.
Once you have that you can then write code that can be stopped after finding a new one, that can be tested on your target number and then continue. If you find a factor, then divide and consider the new number.

Note: Once that works, you want to use one the the many fast prime determinate methods. [They can tell you that a number is prime, but cant find factors if it is not]. That will give you a big speed plus for eliminating if problems when you target number is actually prime.

Thanks pal. I knew that there was a point to limit my prime factor search, but forgot the exact condition. I accept the fact that my math is below avg. Gotta improve a lot on that. I dont mind harsh comments when they teach me something :) I will follow wat you have said.

commented: Nice to see someone who understands constructive criticism and takes it under his belt. rather than maoning about it +3
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.