Goldbach [C/C++]

Goldbach

Publicado por Sergio Spoladore 05/11/2006

[ Hits: 8.011 ]

Homepage: http://yetlinux.blogspot.com

Download goldbach.c

0 0

Denuncie Favoritos Indicar

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.

Esconder código-fonte

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

Scripts recomendados

Campo Elétrico

Biller

Algorítmo para Calcular Raiz Quadrada

Um algoritmo genético para o TSP (Travel Salesman Problem)

Testar o melhor método de organização C (inserção, bolha e shell-sort)

Comentários

[1] Comentário enviado por yetlinux em 15/11/2006 - 04:18h

*** AVISO ***

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

0 0