Help me to solve TLE

[iGEqDjzh]

Problem Statement
After learning sieve of Eratosthenes, Deepak wants to play more with the primes. This time he is trying to print primes between two integers. Help him in this task.
Input Format:

First line contains a single integer 'T' denoting number of test cases. Then 'T' lines follow each containing two integers 'm' and 'n'.
Constraints:

1<=T<=10
1<=m<=n<=1000000000, n-m<=100000

Output Format:

Print the prime numbers from 'm' till 'n' (both inclusive), one number per line and each test case is separated by an empty line.
Sample Input:

2
5 10
11 20

Sample Output:

5
7

11
13
17
19

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

bool primes[M];

int main()
{
    memset(primes,1,sizeof(primes));
    primes[0] = false;
    primes[1] = false;

 for(int i = 2; i < M; i+=1)
 {
     if(primes[i])
     {
         for(long long int j = i*i; j < M; j+=i)
            primes[j] = false;
     }
 }

    int q;
    cin >> q;
    for(int i = 0; i < q; i++)
    {
       long long int n,m;
        cin>>n>>m;
        bool a[m-n+1];
        memset(a,1,sizeof(a));
        
        for(int i = 2; i <sqrt(m); i++)
        {
            if(primes[i])
            {
                for(long long int j = n; j <= m; j++)
                {
                    if(j == i)
                        continue;
                        
                    if(j%i == 0)
                        a[j - n] = false;
                }
            }
            }
        
        
        
        for(int i = 0; i <= m-n; i++)
        {
            if(a[i] && i+n != 1)
                {
                    long long int ans = i+n;
                    cout << ans <<"\n";
                }
        }
        cout<<"\n";
    }
    
    return 0;
}

I have used segmented sieve but it looks like its not fast enough for the given constraints. Can anybody suggest me some different approach or any kind of optimization.