Answers for "how to find the largest prime factor of a number c++"

program to find the largest prime factor of a number

## to find the greatest factor of “A” in the the range up to “B”
1.	#include<iostream>
2.	#include<algorithm>
3.	#include<math.h>
4.	using namespace std;
5.	int main()
6.	{
7.	    int T;
8.	    cin>>T;
9.	    while(T--)
10.	    {
11.	        int A,B;
12.	        cin>>A>>B;
13.	        int mn=A;
14.	        for(int i=1;i<=sqrt(A);i++)
15.	        {
16.	            if(A%i==0)
17.	            {
18.	                if(i<=B)
19.	                {
20.	                    mn=min(mn,A/i);
21.	                }
22.	                if(A/i<=B)
23.	                {
24.	                    mn=min(mn,i);
25.	                }
26.	            }
27.	        }
28.	        cout<<mn<<endl;
29.	    }
30.	    return 0;
31.	}

 use the Sieve of Eratosthenes

prime factorisation of a number in c++

// Function that returns a vector containing all the prime factors of n (25 --> 5, 5)
vector<long long> prime_factorisation(long long n)
{
    //spf is smallest prime factor
    map<long long, long long> spf;
    vector<long long> ans(0);
    for(long long i = 2; i <= n; i++) spf[i] = i;

    for (long long i = 2; i <= n; i++)
        if (spf[i] == i)
            for (long long j = i * i; j <= n; j += i)
                if (spf[j] == j)
                    spf[j] = i;

    while (n != 1)
    {
        ans.push_back(spf[n]);
        n /= spf[n];
    }
    return ans;
}