我怎样才能让我的程序测试哥德巴赫假设在不到 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

罪魁祸首（和往常一样）是错误的质数检查函数。不是说它错了，而是超级慢。

您的函数 czy_pierwsza 计算除数，然后 returns 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;
}

一旦找到一个除数，它就returns0。如果它通过循环直到数的平方根而没有找到一个除数，那么这个数就是质数并且它returns 1.

现在程序在我的机器上运行几秒钟。

我怎样才能让我的程序测试哥德巴赫假设在不到 5 秒内优化

How can i make my program testing goldbach hypotheis optimize in less than 5 sec

c

compiler-optimization