C++ program to find largest prime factor of a number

[harsh4u89]

Please tell me the way to implement a c++ program to find the largest prime factor of a given number.

A hint would work.

Thank you

[Athar]

Keep dividing the number by the smallest possible prime number until it is prime itself.
The result is the largest prime factor.

[harsh4u89]

But this may not be efficient method. Because I have to find the largest prime number of a very big number like 40000000

[harsh4u89]

Any method to find the prime number that could server the purpose here??????

[Athar]

See Google "c++ integer factorization library", first hit.

[harsh4u89]

I am not able to understand the whatever is given in that link

[Athar]

It is a integer factorization library that can do the job for you:

http://sourceforge.net/projects/msieve/

[harsh4u89]

But I want to manually write a program for this

[harsh4u89]

Here is my program ... But its not working for very large value.

#include<iostream>
#include<vector>
#include<cstdlib>
using namespace std;


struct node
{
		unsigned int isPrime:1;
};



double sieve(long num)
{
	struct node s[num];
	//vector<bool> isPrime(num,true);
	//bool isPrime[num]={true};
	for (long i = 2; i*i <= num; i++) 
        {
            if (s[i].isPrime==0) 
            {
                for (long j = i; i*j <= num; j++)
                    s[i*j].isPrime = 1;
            }
        }
	
	for(long i=2;i*i<=num;i++)
	{
	
		if(s[i].isPrime==0)
		{
	
			while(num%i==0)
			{
				num/=i;
			}
		}
	}
	return num;
}
int main()
{
	long i= 600851475143;
	cout<<sieve(i);
	
	return 0;
}

please tell me how to handle how to handle such a big integer

[harsh4u89]

How to handle data as large as 600851475143??


Please suggest some solution

[Zhuge]

Google "bignum library" or something similar.

[bigearsbilly]

are you sure you want to do this?

once you have discovered how to do this in
reasonable time you will be a multi-millionaire!
but,
you will instantly nullify all cryptographic security, bring the world of e-commerce to it's knees, invoking a
financial crisis that will make the recent credit-crunch seem like a picnic.
widespread panic, the world stock markets will cease to function, countries will collapse
bringing the onset of war, famine, pestilence, the civilised world will plunge into a new dark age.
is that what you want?

[harsh4u89]

Heyy there must be some way to do this.

Please suggest some method

[Athar]

You can start with using int64_t (or long long), that'll be big enough to hold 600851475143.
For larger numbers, you'll have to use GMP.

[oz10RXSz]

Read obout Sieve of Eratosthenes.

[harsh4u89]

I tried using int64_t but Semgentation Fault is coming

[harsh4u89]

I tried to use long long on my devc++
But its range is coming out to be equal to that of int
I am using windows Vista home premium

Please sugest some solution

[spaggy]

Find the smallest prime factor and divide the number by that. You'll reach a solution faster, i think

[harsh4u89]

But my program is not running .

Segmentation error is coming

@line

long long int="600851475143";

The range of long long is very very larger than this number but its not working

Please suggest some solution

[R0mai]

"600851475143" is a string literal not a number. Try long long int number = 600851475143;