Find power of biggest prime factor for given number

Question

Given a number N, I need to find if power of biggest prime factor of a number is greater than 1 or not.

N can be as large as 10^18. My approach is as follow :

vector<long long> allfactors;
long long current=2;
while(N>1){
        while(N%current==0){
            allfactors.push_back(current);
            N/=current;
        }
        current++;
        if(current*current > N){
            if(N>1){
                allfactors.push_back(N);
                break;
            }
        }
}
    long long ans=1;
    for(int i=allfactors.size()-2;i>=0;i--){
        if(allfactors[i]!=allfactors[i+1])
            break;
        else
            ans++;
    }
    if(ans>1){
        cout<<"YES\n";
    }
    else{
        cout<<"NO\n";
    }

Can there be better or faster way to do it ? If yes how ? Please help.

i'd start from the root of your number and decrement current step by step. the first found factor is also the biggest. Finding not trivial Primefactors is a hard problem. Have a look at Fermat Factorization. Maybe it could help you with your problem — osanger, Jan 31 '16 at 14:48
@dr_debug You'd need to check that the factor is prime, and it would also be slow for a number where all the prime factors are small. The method used by OP is better. — interjay, Jan 31 '16 at 14:56
@interjay i agree if all prime factors are small, my method is very slow. In other case you are finished after finding the first prime factor. finding primefactors is unfortunately a hard problem. — osanger, Jan 31 '16 at 15:02
have a look at http://stackoverflow.com/questions/23287/largest-prime-factor-of-a-number?rq=1 — osanger, Jan 31 '16 at 15:02
For integers in this range, I'd look at [Pollard's rho](https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm) algorithm, or Brent's variant thereof. First though, find: `gcd(N, pp)`, where `pp` is the product of primes from `(2)` to `(47)` - fitting in a `long long`. — Brett Hale, Jan 31 '16 at 17:29

score 0 · Answer 1 · answered Jan 31 '16 at 16:00

Here's a code that I designed. I found a similar question on projecteuler.net. The number was large enough to make me use long long data type. Hope it helps. :)

    #include<iostream>
    using namespace std;

    unsigned int next(long long,unsigned int,unsigned int);

    unsigned int store[500];

    int main()
    {
        long long k;
        unsigned int max=1;
        unsigned int j,min=0,i;
        store[0]=2;
        cout<<"\nEnter a number : ";
        cin>>k;
        cout<<"\nPrime factors of the entered number are : \n";
        while(k>1)
        {
            for(i=min;i<max;i++)
            {
                if(k%store[i]==0)
                {
                    k=k/store[i];
                    break;
                }
            }
            if(i==max)
            {
                j=next(k,store[max-1],max);
                store[max]=j;
                min=max;
                max++;

            }
        }
        for(i=0;i<max;i++)
            cout<<"\n"<<i<<" "<<store[i];
        return 0;
    }

    unsigned int next(long long k,unsigned int m,unsigned int max)
    {
        long long i,j;
        int flag=0;
        for(i=m+1;i<=k;i++)
        {
            flag=0;
            for(j=0;j<max;j++)
            {
                if(i%store[j]==0)
                {
                    flag=1;
                    break;
                }
            }
            if(flag==0 && k%i==0)
                break;
        }
        return i;
    }

Find power of biggest prime factor for given number

1 Answers1