我如何使我的程序测试哥德巴赫假设在不到5秒的时间内达到最佳状态

Question

我是一年级学生，我们的教授给了我们一个任务，以检查给定范围内的哥德巴赫假设。该程序只需不到5秒即可运行，现在大约需要160秒。如果有人可以告诉我如何使程序更快，或者给出一些简短说明的示例，我将感到非常高兴。这是程序：

int czy_pierwsza(int);
int goldbach(int);
int czy_pierwsza(int x)
{
    int count=0, i;
    if(x<2) return 0;
    for(i=2; i<x-1; i++)
    {  if((x%i)==0) count++;}
    if(count==0)
    return 1;
    else
    return 0;
}
int goldbach(int x)
{int i, y, a=0, tab[2000];
    for(i=2; i<x-1; i++)
    {if(czy_pierwsza(i)==1)
        {
            for(y=2; y<x-1; y++)
            {if(czy_pierwsza(y)==1){
                    if(y+i==x) {  tab[a]=i; tab[a+1]=y;  a+=2; }}}}
        y=a;
    }for(a=0; a<y; a+=2) {printf("(%d %d)", tab[a], tab[a+1]);}
    if(a!=0) return 1; else return 0;
}


int main()
{
    int a=1400, b=1600, x;

    if(a>b) {printf("Incorrect input"); return 1;}
    if(a%2!=0) a+=1;

    for(x=a; x<b+1; x+=2){
        {printf("%d: ", x);
            if(goldbach(x)==1){  printf("\n");}
            else printf("\n");}}


    return 0;

Answer 1

罪魁祸首是（通常）错误的素数检查功能。并不是说它是错误的，而是super slow。

您的函数czy_pierwsza计算除数，然后返回0或1，具体取决于是否存在除数。这等于检查素数（您不需要除数的数量，如果需要它们，也可以更快地对它们进行计数，但这不是重点）]]

用适当的素数检查重写（还有其他方法，但是不需要额外的数组）

int czy_pierwsza(int x)
{
    int i;
    if(x<2) return 0;
    for(i=2; i<(int)(sqrt(x))+1; i++)
    {  if((x%i)==0) return 0;}

    return 1;
}
一旦找到除数，它就返回0。如果它在循环中一直向上到达数字的平方根而没有找到除数，则该数字为质数，并且返回1。

现在程序将在我的计算机上运行几秒钟。