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

Question

I am a 1st year student and our professor gave us a task to check the Goldbach hypothesis in a given range. The program has to take less than 5 seconds to run, now it takes approximately 160s. I would be very glad if somebody could tell me how to make the program quicker, or give some examples with a short description? Here is the program:

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

the culprit is (as usual) a wrong prime checking function. Not that it is wrong, but it's super slow.

Your function czy_pierwsza counts the divisors, then returns 0 or 1 depending if there are divisors or not. That amounts to check for primes (you don't need the number of divisors, and if you need them, you could count them faster too, but that's not the point)

Rewriting with a proper prime check (there are other ways but that one doesn't need an extra array)

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;
}

as soon as it finds a divisor, it returns 0. If it goes through the loop up to square root of the number without finding a divisor, then the number is prime and it returns 1.

Now the program runs in a few seconds on my machine.