c - 如何让我的程序测试哥德巴赫假设在 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 慢。

您的职能 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。

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