Problem with using a _int64 (long long) variable

[arun_lisieux]

Ques:

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
{
	public:
		/*_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(2);
	pno.push_back(3);
	pno.push_back(5);
	pno.push_back(7); // Pushing prime no s within 10 into the vector
	
	for (long long i = 11; i<target; i++)
	{
		if(i%2||i%3||i%5||i%7)
			continue;
		else
			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--)
	{
		if(target%(pno[j]))
		{
			cout << "Largest prime factor of the no '600851475143' : " << pno[j] << endl << endl;
			break;
		} 
	} // 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;
	inst.prime();
}

[StuXYZ]

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.

[arun_lisieux]

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.