6.Prime factorization using Sieve in O(logN)

 #include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>

#include <ext/pb_ds/tree_policy.hpp>

using namespace std;

using namespace __gnu_pbds;

template <class type1>

#define ll long long int

#define endl "\n"

#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>

using ordered_multiset = tree<type1, null_type, less_equal<type1>, rb_tree_tag, tree_order_statistics_node_update>;

// ordered_multiset <ll> kek;(declaration for multiorder set)

// ordered_set o_set;(declaration)

// kek.order_of_key(i);(strictly less then i for multi order set)

// o_set.order_of_key(5) ;(strictly less then i for multi order set)

#define yes cout << "YES\n"

#define no cout << "NO\n"

const ll N = 100000;

ll div1[N+2];

void sieve()

{

    for (ll i = 1; i <= N; i++)

    {

        div1[i] = -1;

    }

    for (ll i = 2; i <= N; i++)

    {

        if (div1[i] == -1)

        {

            for (ll j = i; j <= N; j += i)

            {

                div1[j] = i;

            }

        }

    }

}

int main()

{

    ios_base::sync_with_stdio(0);

    cin.tie(0);

    cout.tie(0);

    sieve();

    for (ll i = 1; i <= 20; i++)

    {

        cout << div1[i] << " ";

    }

    return 0;

}