难度2：素数距离问题

描述
现在给出你一些数，要求你写出一个程序，输出这些整数相邻最近的素数，并输出其相距长度。如果左右有等距离长度素数，则输出左侧的值及相应距离。
如果输入的整数本身就是素数，则输出该素数本身，距离输出0
输入
第一行给出测试数据组数N(0<N<=10000)
接下来的N行每行有一个整数M(0<M<1000000)，
输出
每行输出两个整数 A B.
其中A表示离相应测试数据最近的素数，B表示其间的距离。
样例输入
3
6
8
10
样例输出
5 1
7 1
11 1
-----------------------------------------标准分界线----------------------------------------------
第一次写这个题目的程序，我忘了什么是素数了，然后百度了下。。。。所谓素数就是大于1的数，且该数只能被1和其本身整除。
-----------------------------------------------------------------------------------------------------
以下是我自己写的几次程序，前几次的程序在上传OJ时出现了超时运行的错误导致无法上传成功。。。。。。。。。。。（这个OJ是在为难我胖虎。。。。。。。。。。。）
1）

 1 #include<iostream>
 2 #include<cmath>
 3 
 4 using namespace std;
 5 
 6 int isPrime(int n)
 7 {
 8     if (n < 2)
 9         return 0;
10     else
11     {
12         for (int i = 2; i <= sqrt(n); i++)
13         {
14             if (n%i == 0)
15                 return 0;
16         }
17         return 1;
18     }
19 }
20 
21 int main()
22 {
23     int M, N;
24     cin>>N;
25     while (N--)
26     {
27         for (int i = 0; i < N; i++)
28         {
29             int A, B;
30             cin >> M;
31 
32             for (int i = 1; i < 1000000; i++)
33             {
34                 if (isPrime(M))
35                 {
36                     cout << M << " " << 0 << endl;
37                     break;
38                 }
39                 A = M - i;
40                 if (isPrime(A))
41                 {
42                     cout << A << " " << i << endl;
43                     break;
44                 }
45                 B = M + i;
46                 if (isPrime(B))
47                 {
48                     cout << B << " " << i << endl;
49                     break;
50                 }
51             }
52         }
53     }
54     return 0;
55 }

 1 #include<iostream>
 2 #include<cmath>
 3 
 4 using namespace std;
 5 
 6 int isPrime(int n)
 7 {
 8     if (n < 2)
 9         return 0;
10     else
11     {
12         for (int i = 2; i <= sqrt(n); i++)
13         {
14             if (n%i == 0)
15                 return 0;
16         }
17         return 1;
18     }
19 }
20 
21 int main()
22 {
23     int M, N;
24     cin>>N;
25       if(N>0&&N<=10000) 
26        {
27            while (N--)
28      {
29         for (int i = 0; i < N; i++)
30         {
31             int A, B;
32             cin >> M;
33 
34             for (int i = 1; i < 1000000; i++)
35             {
36                 if (isPrime(M))
37                 {
38                     cout << M << " " << 0 << endl;
39                     break;
40                 }
41                 A = M - i;
42                 if (isPrime(A))
43                 {
44                     cout << A << " " << i << endl;
45                     break;
46                 }
47                 B = M + i;
48                 if (isPrime(B))
49                 {
50                     cout << B << " " << i << endl;
51                     break;
52                 }
53             }
54         }
55       }
56       }
57       else
58       {
59             cout<<"Input Error!"<<endl;
60       }
61     return 0;
62 }

以上的程序都是超时但是能进行运行的，就是运行速度太慢。（我也很绝望啊。。。。。。。。。。。。。）
这是改进后的程序：

 1#include<iostream>
 2 #include<cmath>
 3 
 4 using namespace std;
 5 
 6 int isPrime(int n)
 7 {
 8     if (n < 2)
 9         return 0;
10     else
11     {
12         for (int i = 2; i <= sqrt(n); i++)
13         {
14             if (n%i == 0)
15                 return 0;
16         }
17         return 1;
18     }
19 }
20 
21 int main()
22 {
23     int M, N;
24
25     while (cin>>N)
26     {
27         for (int i = 0; i < N; i++)
28         {
29             int A, B;
30             cin >> M;
31 
32             for (int i = 1; i < 1000000; i++)
33             {
34                 if (isPrime(M))
35                 {
36                     cout << M << " " << 0 << endl;
37                     break;
38                 }
39                 A = M - i;
40                 if (isPrime(A))
41                 {
42                     cout << A << " " << i << endl;
43                     break;
44                 }
45                 B = M + i;
46                 if (isPrime(B))
47                 {
48                     cout << B << " " << i << endl;
49                     break;
50                 }
51             }
52         }
53     }
54     return 0;
55 }

时间稍微缩短一些，勉强通过测试。。。。。。。。。。。

----------------------------------------------------------------------------------------------------------------------------------------------------------------------

这个是待解决的程序：（我想缩短更多的时间）

#include<iostream>
#include<cmath>

using namespace std;

int isPrime(int n)
{
    if (n < 2)
        return 0;
    else
    {
        for (int i = 2; i <= sqrt(n); i++)
        {
            if (n%i == 0)
                return 0;
        }
        return 1;
    }
}

int main()
{
    int M, N;
    cin >> N;
    while (N--)
    {
            cin >> M;
            int dis = 0;
            for(int i=1;i<1000000;i++)
            {
                if ( isPrime(M - dis))
                {
                    cout << M - dis << " " << dis << endl;
                    break;
                }
                else if (isPrime(M + dis))
                {
                    cout << M - dis << " " << dis << endl;
                    break;
                }
                dis++;
            }
        }
    return 0;
}

这个程序的运行测试的几组都不行，比如1,10.。。。。。