Dividing Machine- DIVMAC

Problem Link

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

#define LL long long
#define sf(i) scanf("%d", &i)
#define pf(i) printf("%d ", i);
const int N = 1000000;
const int M = 100000;
int leastPrime[N + 1];
bool prime[N + 1];

int arr[M + 1];
int seg[3 * M];


void sieve()
{
    memset(prime, true, sizeof prime);
   for(int i = 0; i <= N; i++)
   {
       leastPrime[i] = N;
   }

    for(int i = 2; i * i <= N; i++)
    {
        if(prime[i])
        {
            for(int j = i * i; j <= N; j += i)
            {
                prime[j] = false;
                leastPrime[j] = min(i, leastPrime[j]);
            }
        }
    }

    leastPrime[0] = 1;
    leastPrime[1] = 1;
    leastPrime[2] = 2;
    for(int i = 3; i <= N; i+= 2)
    {
        if(prime[i])
        {
            leastPrime[i] = i;
        }
    }
}

void buildTree(LL index, int low, int high)
{
    if(low > high)
        return;
    if(low == high)
    {
        seg[index] = leastPrime[arr[low]];
    }
    else
    {
        int mid = (low + high) / 2;
        buildTree(2 * index + 1, low, mid);
        buildTree(2 * index + 2, mid + 1, high);

        seg[index] = max(seg[2 * index + 1], seg[2 * index + 2]);
    }
}

void updateTree(int low, int high, int l, int r, LL index)
{
    if(seg[index] == 1)
        return ;
    if(low > r || high < l || low > high)
        return;
    if(low == high)
    {
        int val;
        if(leastPrime[arr[low]] != 0)
        {
            val = arr[low] / leastPrime[arr[low]];
            arr[low] = val;
            seg[index] = leastPrime[val];
        }
        else
        {
            seg[index] = 1;
        }

    }
    else
    {
        int mid = (low + high) / 2;
        updateTree(low, mid, l, r, 2 * index + 1);
        updateTree(mid + 1, high, l, r, 2 * index + 2);

        seg[index] = max(seg[2 * index + 1], seg[2 * index + 2]);
    }
}

int getVal(int low, int high, int ql, int qh, LL index)
{
    if(seg[index] == 1)
        return 1;
    if(ql <= low && qh >= high)
    {
        return seg[index];
    }
    if(ql > high || qh < low || low > high)
    {
        return 0;
    }

    int mid = (low + high) / 2;
    return max(getVal(low, mid, ql, qh, 2 * index + 1), getVal(mid + 1, high, ql, qh, 2 * index + 2));
}

int main()
{
    int t;
    int n, m, type, l, r;

    sieve();

    sf(t);
    while(t--)
    {
        sf(n), sf(m);
        for(int i = 0; i < n; i++)
        {
            sf(arr[i]);
        }

        buildTree(0, 0, n - 1);

        for(int i = 0; i < m; i++)
        {
            sf(type), sf(l), sf(r);
            if(type == 1)
            {
                int res =  getVal(0, n - 1, l - 1, r - 1, 0);
                pf(res);

            }
            else
            {
                updateTree(0, n - 1, l - 1, r - 1, 0);
            }
        }

        printf("\n");
    }
    return 0;
}