超时啊啊
#include<bits/stdc++.h>
using namespace std;
int a[10010];
bool flag[1000010];
int main()
{
int n,q,l,r,sum=0,k=1;
scanf("%d",&n);
flag[0] = flag[1] = true;
for(int i = 2;i <= 1000010;i++)
{
if(flag[i] == false)
{
for(int j=2;j<=1000000/i;j++)
{
flag[i*j] = true;
}
}
}
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
scanf("%d",&q);
for(int i=1;i<=q;i++)
{
scanf("%d%d",&l,&r);
for(int j=l;j<=r;j++)
{
if(flag[a[j]]==false)
sum++;
}
printf("%d\n",sum);
sum=0;
}
return 0;
}