Yet Another Cute Girl - PRETNUM

Problem Link

#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>
using namespace std;
#define LL long long

const int N = 1000010;
bool prime[N + 1];
vector<int> v;

void sieve()
{
for(int i = 2; i <= N; i++)
{
prime[i] = true;
}

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

v.push_back(2);
for(int i = 3; i <= N; i += 2)
{
if(prime[i])
{
v.push_back(i);
}
}
}

LL getNumDiv(LL num)
{
    /* if prime factor of n is p1^k1 p2 ^ k2 then prime factor of n^2 would be
        (p1^k1 p2 ^ k2)^2 = p1^(2k1) p2^(2k2)
        so number of divisors of n^2 would be (2 * k1 + 1) * (2 * k2 + 1) ...
        if n is a prime number number then number of divisors of n^2 would be 3.
    */

LL res = 1;
for(int i = 0; i < v.size() && v[i] * v[i] <= num; i++)
{
if(num % v[i] == 0)
{
int count = 0;
while(num % v[i] == 0)
{
count++;
num /= v[i];
}

res = res * (2 * count + 1LL);
}

}

if(num != 1)
res *= 3;

return res;
}

LL segmented_sieve(LL a, LL b)
{
    int count = 0;

if(b<2) return 0;
if(a < 3)
    {
        a = 3;
        count++;
    }

    if(a % 2 == 0)
    {
        a++;
    }

bool prime1[b - a + 2];
memset(prime1, true, sizeof prime1);

for(int i = 0; i < v.size() && v[i] * v[i] <= b; i++)
{
LL low = floor(a / v[i]) * v[i];
if(low < a){
low += v[i];
}

        //cout << "Low value = " << low << endl;
for(LL j = low; j <= b; j += v[i])
{
if(j != v[i])
prime1[j - a] = false;
}
}

for(int i = 0; i <= b - a; i += 2)
{
    //cout << "prime = " << i + a << "value = " << prime1[i] << endl;
if(prime1[i])
count++;
}

   // cout << " count = " << count << endl;
return count;
}


int main()
{
int t;

LL l, r;
int res;
sieve();
cin >> t;
while(t--)
{
cin >> l >> r;

if(l == 1)
l++;
res = 0;

res = segmented_sieve(l, r);

LL k = sqrt(l);
for(LL i = k; ; i++)
{
if(i * i > r)
break;
if(i * i >= l)
{
if(prime[getNumDiv(i)])
{
res++;
}
}
}

cout << res << endl;
}

return 0;
}