Goldbach
Para economizar espaço com explicações:
http://yetlinux.blogspot.com/2004/12/goldbach.html
Este programa imprime os modos de escrita de um número par como soma de dois números primos. Também quantos modos possíveis.
Bom para quem se liga em programação e teoria dos números.
http://yetlinux.blogspot.com/2004/12/goldbach.html
Este programa imprime os modos de escrita de um número par como soma de dois números primos. Também quantos modos possíveis.
Bom para quem se liga em programação e teoria dos números.
Descrição
Para economizar espaço com explicações:
http://yetlinux.blogspot.com/2004/12/goldbach.html
Este programa imprime os modos de escrita de um número par como soma de dois números primos. Também quantos modos possíveis.
Bom para quem se liga em programação e teoria dos números.
http://yetlinux.blogspot.com/2004/12/goldbach.html
Este programa imprime os modos de escrita de um número par como soma de dois números primos. Também quantos modos possíveis.
Bom para quem se liga em programação e teoria dos números.
#include <stdio.h>
#include <math.h>
int IsPrime (int p){
int j=0;
if (p%2 == 0) return 0;
for (j=3; j<=1+(int)sqrt(p) && (p%j!=0); j+=2);
return (p%j!=0);
}
int main (int argc, char *argv[]) {
int i=0, m=0, n=0;
if (argc!=2){
puts ("use ./goldbach "); exit(1);
}
n=atoi(argv[1]);
if (n<=4){
puts ("numero muito pequeno"); exit(1);
}
if (n%2==1){
puts ("numero impar"); exit(1);
}
printf ("%d:", n);
for (i=3; i<=n/2; i+=2) {
if (IsPrime(i) && IsPrime(n-i)) {
printf("\n\t %ld = %ld + %ld",n, i, n-i);
m++;
}
}
printf ("\n%d representacoes distintas\n", m);
return 0;
}
Na época em que fiz este código (OUT/NOV 2004) estava me adequando à filosofia de publicar um código mesmo que não esteja 100% livre de falhas. Esqueci-me ainda de corrigir o que estava pendente.
Quem não estiver acostumado com o GCC, segue como compilar:
$ gcc goldbach.c -lm -o goldbach
A opção -lm indica a linkedição com a biblioteca libm.a, que possui as rotinas para a função SQRT.
Portanto, para quem se interessou, publicarei aqui neste espaço o que eu for encontrando de errado.
15/11/2006:
A função IsPrime não avalia se o número 2 é primo. O loop de avaliação de primalidade com apenas um "for" e sem comandos adicionais é muito elegante, porém ele não avalia os números 3 e 5 como primos. A solução mais objetiva foi:
int IsPrime (int p){
int j=0;
if (p == 2 || p == 3 || p == 5) return 1; // código novo
if (p%2 == 0) return 0;
for (j=3; j<=1+(int)sqrt(p) && (p%j!=0); j+=2);
return (p%j!=0);
}