ujjalroys.blogspot.com

 prime factorisation in O(sqrt(n)) in cpp

#include<bits/stdc++.h>

using namespace std;

int main()

{

    int n,i;

    cin>>n;

    vector<int> v;

    for(i=2;i*i<=n;i++)

    {

        while(n%i==0)

        {

            v.push_back(i);

            n/=i;

        }

    }

    if(n>1)v.push_back(n);

    for(auto u : v)cout<<u<<" ";

    cout<<endl;

    return 0;

}