输出所有完美数，时间超限怎么解决？

Question

Oj显示时间超限，怎么样才能优化，减少时间呢？求指点，谢谢了。

Answer 1

这是一段计算到第8个完全数的代码，最快的寻找完美数算法，利用欧拉公式和卢卡斯-莱默检验法，供参考：

//利用欧拉公式和卢卡斯-莱默检验法
#include <stdio.h>
#include <string.h>
int isPrime(int N)
{
    if(N < 4)        return N > 1;
    if((N & 1) == 0) return 0;
    for (int i = 3;i * i <= N;i += 2)
        if ((N % i) == 0)   return 0;
    return 1;
}
int primality(int N, __int64 M)
{
    if(N == 2) return 1;
    __int64 s = 4;
    for(int i = 0;i < N - 2;i++)
        s = (s * s - 2) % M;
    return s == 0;
}
int main()
{
    char s[21] = {0};
    int i, cnt = 0;
    __int64 M, t;
    for (i = 2;i < 32; i++){//2 - 2^31-1
        M = (1 << i) - 1;
        t = M << (i - 1);
        if(isPrime(i) && primality(i, M)){
            sprintf(s, "%I64d", t);
            cnt++;
            printf("第%d个%d位数:%s\n",cnt,strlen(s),s);
        }
    }
    return 0;
}