Conjectura de goldbach

[jpmor82]

Queria fazer um programa para testar a conjectura de goldbach em c, http://www.ieeta.pt/~tos/goldbach.html, mais precisamente é para provar que todos os números pares superiores a 4 sao soma de dois primos, até um número introduzido pelo utilizador, se alguem tiver uma proposta interessante para este programa agradecia.

[mogers]

Essa não é bem a conjectura de Goldbach, passo a citar:

In 1742, Christian Goldbach, a German amateur mathematician, sent a letter to Leonhard Euler in which he made the following conjecture:

Every number greater than 2 can be written as the sum of three prime numbers.

Goldbach cwas considering 1 as a primer number, a convention that is no longer followed. Later on, Euler re-expressed the conjecture as:

Every even number greater than or equal to 4 can be expressed as the sum of two prime numbers.

É bastante simples. Podes fazer assim:

1) Geras os números primos até N com o crivo de erastotenes

2) Para cada numero par i de 4 a N, pegas nos números primos (num_primo) menores ou iguais a  i / 2  e verificas  se o número  n2 = i - num_primo é primo.

😁

[jpmor82]

Eu ja fiz assim:

#include <stdio.h>

int primo(int n)
{
int i;

for (i = 2; i < n; i++)
{
if (n % i == 0)
	return 0;
i++;
}

return 1;
}

void main(void)
{
int a, i, j=0,k;

do
{
printf("Introduza um numero par superior a 4: ");
scanf("%d", &a);
}while((a<=4) || (a%2!=0)) ; 

for(k=4; k<=a ; k=k+2)
{
for(i=1 ; i<=k/2 ; i++)
{
	if(primo(i))
		if(primo(k-i))
			j=k-i;
}
printf("O numero %d, e a soma dos primos %d + %d\n", k, k-j, j);
}

system("PAUSE");
}

Mas agora gostaria de ideias para por o programa mais rapido, secalhar com alocaçao dinamica de memoria, e introduzir todos os primos nessa variavel dinamica, e assim ia somando os primo, que acham?

[mogers]

A verificação do numero primo está errada. Estás a incrementar a variavel 'i' , duas vezes seguidas. 'i' vai tomar os valores 2,4,6,8...

Podes ir só até a raiz quadrada do número (acho que no forum também já foi discutido como testar a primalidade de um número)

Isso assim fica muito lento. a minha ideia era usar o crivo de erastotenes para calcular os numeros primos.

vai a secção de algoritmia e logica.. o crivo está explicado lá. Para o usares precisas de limitar o número que o utilizador pode escolher (10 , 100 , 200, 12344 , 1000000 , o que for)

depois disto podes colocar os numeros primos num array, e poupas grande parte do ciclo de 1 a k/2.

Ainda podes tornar isso mais rapido com custo de memória, se pré-calculares... mas deixa isso para depois 😉

Edit: Alocação dinamica de memória é lenta (super lenta comparando com a alocação normal). É uma coisa a evitar ao máximo se estiveres concentrado na eficiência.

[jpmor82]

Ja agora como posso  calcular o tempo que o programa demora a correr?? que funçao posso usar para calcular o tempo?

[Rui Carlos]

Ja agora como posso  calcular o tempo que o programa demora a correr?? que funçao posso usar para calcular o tempo?

Em Unix podes usar o comando time.

[mogers]

Em windows é muito mais chato... a única forma que conheço é

#include <time.h>

// variavel global
clock_t start = clock();

int main()
{
// codigo

// ...



// final
clock_t ends = clock();
printf("Tempo de execucao: %.5f seg\n\n",(double) (ends - start) / CLOCKS_PER_SEC);
return 0;
}

[TheDark]

Isso é em C geral. Para usar a API do Windows, que é muito mais precisa, utiliza:

#include <windows.h>

void main() {
LARGE_INTEGER tempoInicial, tempoFinal, freq;
float tempoTotal;
QueryPerformanceCounter(&tempoInicial);

//código cujo tempo queres contar

QueryPerformanceCounter(&tempoFinal);
QueryPerformanceFrequency(&freq);
tempoTotal = (float)(tempoFinal.QuadPart - tempoInicial.QuadPart)/freq.QuadPart;
}

Mais detalhes aqui

[jpmor82]

Obrigado pessoal

Mas onde esta:

tempoTotal = (float)(tempoFinal.QuadPart - tempoInicial.QuadPart)/freq;

dá-me erro em '/'

é isto que diz:

1>.\goldbach.c(57) : error C2088: '/' : illegal for union

[TheDark]

Hm, só vi isto hoje. Já está corrigido!

[Exata0mente]

Olá!

Segue uma outra forma da validação da conjectura de goldbach:

 

#include <stdio.h>
#define MIN 700
#define MAX 1100
#define TRUE 1
#define FALSE 0

int confirma_goldbach(int);
int e_primo(int);
int mostra_goldbach(int, int, int);

int main(){

    register int i;

    for(i = MIN; i <= MAX; i += 2){
        if(confirma_goldbach(i))
            continue;
    }


return 0;
}

int confirma_goldbach(int num){

    register int i, j = 2;

    for(i = 2; i + j <= num; i++){
        if(e_primo(i))
            for(j = 2; j < num; j++){
                if(e_primo(j)){
                    if(mostra_goldbach(i, j, num))
                        return TRUE;
                }
            }
            j = 2;
    }

return FALSE;
}

int e_primo(int num_teste){

    register int i, cont_div;

    cont_div = num_teste == 1 ? 1 : 2;

    for(i = 2; i <= num_teste / 2; i++){
        if(num_teste % i == 0){
            cont_div++;
            break;
        }
    }

return (cont_div == 2 ? TRUE : FALSE);
}

int mostra_goldbach(int primo1, int primo2, int num_teste){

    if(primo1 + primo2 == num_teste){
        printf("%3d + %3d = %3d\n", primo1, primo2, num_teste);
        return TRUE;
    }
    else{
        return FALSE;
    }
}