哥德巴赫猜想，代码优化

Question

哥德巴赫猜想，不是想证明这个结论，而是对于任给的一个不小于6的偶数，来寻找和等于该偶数的所有素数对。做好了这件实事,就能说明这个猜想是成立的。
要求程序定义一个prime()函数和一个main()函数，prime()函数判断一个整数n是否是素数，其余功能在main()函数中实现。
int prime(int n)
{
//判断n是否为素数， 若n为素数，本函数返回1，否则返回0
}
提交网站时，时间超限

#include <stdio.h>
#include <math.h>

int prime(int n);
int main(int argc, char const *argv[]){
    int m,i,j;
    scanf("%d", &m);
    
    for( i=2; i<m; i++ ){
        
        for( j=2; j<m; j++ ){
            if( prime(i)&&prime(j)){//若i和j都是素数 
                if( i+j==m&&i<=j )//判断去重 
                    printf("%d %d\n", i,j);
            }
        }
    }
    return 0;
}
int prime(int n){//判断是否是素数 
    int flag=1;
    for( int i=2; i<=sqrt(n); i++ ){
        if( n%i==0||n==1 )
            flag=0;
    }
    return flag;
}

结果正确

解决时间超限

解决方案
改用单层循环i，利用循环得出另一位j
代码如下

#include <stdio.h>
#include <math.h>

int prime(int n);
int main(int argc, char const *argv[]){
    int m,i,j;
    scanf("%d", &m);
    
    for( i=2; i<m; i++ ){
        j=m-i;
            if( prime(i)&&prime(j)){//若i和j都是素数 
                if( i<=j )//判断去重 
                    printf("%d %d\n", i,j);
        }
    }
    return 0;
}
int prime(int n){//判断是否是素数 
    int flag=1;
    for( int i=2; i<=sqrt(n); i++ ){
        if( n%i==0||n==1 )
            flag=0;
    }
    return flag;
}

Answer 1

修改如下，供参考：

#include <stdio.h>
#include <math.h>
int prime(int n);
int main(int argc, char const* argv[]) {
    int m, i, j, t;
    scanf("%d", &m);

    for (i = 2, t = m / 2; i <= t; i++) {   //for (i = 2; i < m; i++) 修改
        j = m - i;
        if (prime(i) && prime(j)) {//若i和j都是素数 
            if (i <= j)//判断去重 
                printf("%d %d\n", i, j);
        }
    }
    return 0;
}
int prime(int n) {//判断是否是素数  修改
    if (n <= 3)  return n > 1;
    int flag = (int)sqrt(n);
    for (int i = 2; i <= flag; i++) 
        if (n % i == 0) return 0;
    return 1;
}