Finding prime factors

user_1218732 0
Viewed 44153
#include <iostream>
using namespace std;

void whosprime(long long x)
{
    bool imPrime = true;

    for(int i = 1; i <= x; i++)
    {
        for(int z = 2; z <= x; z++)
        {
            if((i != z) && (i%z == 0))
            {
                imPrime = false;
                break;
            }
        }

        if(imPrime && x%i == 0)
            cout << i << endl;

        imPrime = true;
    }    
}

int main()
{
    long long r = 600851475143LL;
    whosprime(r);  
}

I'm trying to find the prime factors of the number 600851475143 specified by Problem 3 on Project Euler (it asks for the highest prime factor, but I want to find all of them). However, when I try to run this program I don't get any results. Does it have to do with how long my program is taking for such a large number, or even with the number itself?

Also, what are some more efficient methods to solve this problem, and do you have any tips as to how can I steer towards these more elegant solutions as I'm working a problem out?

As always, thank you!

factorization prime-factoring primes c++
12 Answers

Simple way :

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;

ll largeFactor(ll n)
{
        ll ma=0;
        for(ll i=2; i*i<=n; i++)
        {
            while(n%i == 0)
            {
                n=n/i;
                ma=i;
            }
        }
        ma = max(ma, n);
        return ma;
}

int main() 
{
    ll n;
    cin>>n;
    cout<<largeFactor(n)<<endl;
    return 0;
}

Implementation using prime sieve ideone.

user_67144300

Since 600851475143 is out of scope for int as well as single long type wont work here hence here to solve we have to define our own type here with the help of typedef. Now the range of ll is some what around 9,223,372,036,854,775,807.

typedef long long int LL

user_101206220
Related