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();
}

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 …

## 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 learning and sharing knowledge.