Golu And Sweetness - Euler Totient Function

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);


bool prim(ll x) {

  if (x < 2) return false;
   
   if(x%2==0 || x%3==0||x%5==0 ) return false;
   
   
  for (ll  i = 5; i * i <= x; i=i+6)
    {
    if (x % i == 0||(x+2)%i==0)
    {
      return false;
    }
  }
  return true;
}
bool check(ll x)
{
    if(x<2)
    return false;
    if(x==2||x==3||x==5)
    return true;
     if(x%2==0 || x%3==0||x%5==0 ) return false;

     return prim(x);
}
int phi(int n)
{
    int ret=n;

    for(int i=2;i*i<=n;i++)
    {
        if(n%i==0)
        {
            while(n%i==0)
            {   
                n/=i;
            }
          
            ret -= ret/i;
        }
    }

    if(n>1)
    {   
        ret -= ret/n;
    }

    return ret;
}
ll al[1000005];
int main()
{   IOS;

   int n,m,b;
   cin>>n>>m;
   for(int i=1;i<=n;++i)
   {
       cin>>b;
   if(check(phi(b)))
   al[i]=1;
   al[i]+=al[i-1];
   }
  
   
    int x,y;
     while (m--)
   {
    cin>>x>>y;
    cout<<al[y]-al[x-1]<<endl;
   }
   
}