Самый быстрый способ подсчета разделов Гольдбаха в Pari/GP

Question

Я пытаюсь подсчитать количество разделов Гольдбаха и ударов о стену, когда n велико. Любые советы о том, как я могу сделать этот код как можно быстрее, были бы полезны. Вот лучшее, что мне удалось сделать до сих пор:

n=1000; x=0; forprime(i=n, 2*n-3, if(isprime(2*n-i), x++; ); ); print(n," ",x);

Answer 1

Попробуйте адаптировать этот алгоритм

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

void sieve_prime(bool *prime5mod6, bool *prime1mod6,int n,int imax)
{
    int i, i1;   
    
    for(i=1;(6*i-1)*(6*i-1)<=n;i++){
        if(prime5mod6[i]==false){
            for(i1=6*i*i;i1 <= imax+2*i;i1+=(6*i-1)){
                if(i1<=imax)
                    prime5mod6[i1]=true;
                prime1mod6[i1-2*i]=true;        
            }
        }
        if(prime1mod6[i]==false){
            for(i1 = 6*i*i;i1<=imax;i1+=(6*i+1)){
                prime5mod6[i1]=true;       
                if(i1<=imax-2*i)
                    prime1mod6[i1+2*i]=true;        
            }
        }
    }
}


int count_partition(bool *prime5mod6, bool *prime1mod6, int n)
{
    int i,imax, count=0, nmod6;

    imax=(n-n%6)/6;
    nmod6=n%6;

    if(nmod6==0){
        for(i=1;i<imax;i++){
                if(prime5mod6[i]==false && prime1mod6[imax-i]==false){
                    count++;
                }
        }
    }
    else if(nmod6==2){
           for(i=1;i<=(imax-2+imax%2)/2;i++){
                if(prime1mod6[i]==false && prime1mod6[imax-i]==false){
                   count++;
                }
            }

            if(prime1mod6[(imax+imax%2)/2]==false && imax%2==0){
                count++;
            }
            if (prime5mod6[imax]==false){
                count++;
            } 
    }
    else  if(nmod6==4){
        for (i=1; i<=(imax-imax%2)/2; i++){
            if(prime5mod6[i]==false && prime5mod6[imax+1-i]==false){
                 count++;
            }
        }
        if(prime5mod6[(imax+imax%2)/2]==false && imax%2==1){
            count++;
        }
    if(prime1mod6[imax]==false){
          count++;
        } 

    }
    return count;
}


int main()
{
    int  n,nmin,nmax,i,imax,count;
    bool *prime5mod6,*prime1mod6;
    do {
        printf("Insert Nmin > 6 : ");
        scanf("%d", &nmin);
    }        
    while (nmin<=6);
    do {
        printf("\nInsert Nmax >= %d : ",nmin+nmin%2);
        scanf("%d", &nmax);
    }        
    while (nmax<nmin+nmin%2);

    imax=(nmax-nmax%6)/6+1;
    prime5mod6 = (bool *) calloc(imax+1,sizeof(bool));
    prime1mod6 = (bool *) calloc(imax+1,sizeof(bool));
    sieve_prime(prime5mod6, prime1mod6, nmax,imax);

    for(n=nmin+nmin%2;n<=nmax;n+=2){
      count = count_partition(prime5mod6,prime1mod6,n);
      printf("\n %d  -  %d",n,count);
    }
    free(prime5mod6);
    free(prime1mod6);
    return 0;
}