Conjetura de Goldbach en C++

[seryioo]

Buenas, aquí sigo con programación I. Tengo que hacer un ejercicio en el que hay que introducir un número n, par, en el teclado y descomponerlo en la suma de 2 números primos.
Lo único que puedo manejar son bucles y crear subprogramas.

Código (cpp) [Seleccionar] Expandir

/*
8) Defínase una función sin resultado factorizar(n) que calcule los factores primos de su
argumento n para números mayores o iguales que 2 y los escriba en la pantalla. Defínase
también otra función sin resultado sumaDePrimos(n) que descomponga un número n par
y mayor que 2 en suma de dos números primos y los presente en pantalla. (Según la
conjetura de Goldbach, todo número par mayor que 2 siempre se puede descomponer en
suma de dos números primos).
*/

#include <iostream>
using namespace std;

void factorizar(int n){
   for(unsigned a=3; a<n; a++){
       if(n%a==0) cout<<a<<endl;
   }

}

//--------------------------------------------------------------

void sumadeprimos(int n){   //ESTO ES LO QUE TENGO MAL, HABIA PENSADO QUE SE FUERA COMPROBANDO
                                  // LA SUMA DE DOS PRIMOS HASTA QUE FUERA IGUAL A "n" PERO O SE PASA DE "n" O NO LLEGA
   int suma=0;
   if(n%2==0){  //si n es par
       int contador=0;

       while(suma<n){ //bucle que controla la suma y se tendría que ejecutar hasta que se cumpliera la conjetura de Goldbach
           int a=3;

           while(contador<2 and a<n){  //bucle en el que se va haciendo la suma de primos. "contador" se reinicia cada 2 ciclos
               if(n%a==0){
                   suma+=a;
                   ++contador;
                       cout<<suma<<endl;
               }
               ++a;
           }
           contador=0;
       }
   }
   cout<<suma<<endl;
}
   
//------------------------------------------------------------------- 

int main(){
   int n;
   cout<<"n = ";
   cin>>n;
   cout<<"Factores primos de n: "<<endl;
   factorizar(n);
   cout<<endl;
   cout<<"Descomposicion en la suma de 2 factores primos de n par "<<endl;
   sumadeprimos(n);



return 0;
}


[joecarl]

Haz una función que compruebe si un número es primo.
Haz otra función que recorra todos los número menores que "n", en cada iteración usa la función q creaste para comprobar que tanto " i" como "n - i" son primos. Pseudo código:

HallarSuma(int n)
  Para i =0 hasta n
    Si esPrimo(i) y esPrimo(n-i)
      Mostrar i y n-i
    Fin si
  Fin para
Fin hallarSuma

[seryioo]

Vale, algo más claro, pero sigo teniendo la duda de cómo hacer la función "sumadeprimos" ya que tendría que hacer combinaciones de 2 números primos hasta que su suma fuera n, pero no se como hacer eso.

Adjunto el código.

Código (cpp) [Seleccionar] Expandir

#include <iostream>
using namespace std;

void factorizar (int n);

void sumadeprimos(int n);

int primo(int n);

//---------------------

int main(){
   int n;
   cout<<"Introduce n: ";
   cin>>n;
   cout<<"Factores primos de n:"<<endl;
   factorizar(n);



return 0;
}

//----------------------

int primo(int m){
   int incremen=2;
   bool primo=true;
   while(primo && incremen<m){
       if(m%incremen==0) primo=false;
       ++incremen;
   }
   if (primo) return m;
   else return 0;
}

void factorizar (int n){ //factores primos de su argumento n para números mayores o iguales que 2 y los escriba en la pantalla.
  for(unsigned m=3; m<n; m++){
       if (primo(m)!=0) cout<<primo(m)<<endl;
  }
}


void sumadeprimos(int n){ //descomponga un número n par y mayor que 2 en suma de dos números primos y los presente en pantalla.
   if(n%2==0){ //ok
       
   }
   
}

[engel lex]

sobre el numero primo, este es el algoritmo que llevo usando un tiempo por cosas de eficiencia

Código (cpp) [Seleccionar] Expandir

int primo(int n){
int i;
if(n<=3) return n>=2;

if(n%2==0 || n%3==0) return false;

for(i=5;i*i<=n;i+=6){
if(n%i==0 || n%(i+2)==0) return false;
}
return true;
}


para sumadeprimos, recomiendo lo siguiente

sabemos que n debe ser par, los 2 números mayores que suman uno par, es el numero /2

de ahí puedes empezar a buscar por el numero/(2-i), siendo i=1 al inicio, el otro numero es eso numero-(numero/(2-i))... así vas incrementando 1 a i para ver si es suma de 2 primos... si numero/2-i==1, no existen 2 primos que sumados den tu resultado

[joecarl]

Tal y como te indiqué en el pseudocode:

HallarSuma(int n)
 Para i =2 hasta n
   Si esPrimo(i) y esPrimo(n-i)
     Mostrar i y n-i
   Fin si
 Fin para
Fin hallarSuma

Que sería:

Código (c++) [Seleccionar] Expandir


void sumadeprimos(int n){
 int i;
 for(i=2;i<n;i++){
   if (primo(i) && primo (n-i)){
     cout << n << " = " << i << " + " << n-i << endl;
   }
 }
}

No he probado el código pero imagino que funcionará, ese código es que invertirá menos tiempo en ejecutarse pero quizá haya que refinarlo un poco.

EDIT: he cambiado i=0 por i=2 como condicion inicial en el for ya que ni el 0 ni el 1 son primos segun wikipedia.

[seryioo]

Si, tu codigo funciona perfectamente, ahora estoy intentado entenderlo...

No entiendo bien qué se está haciendo en el if y por qué un primo es primo(i) y otro primo(n-i)

PD: Vale , ya se lo que haces

Gracias engel lex y joecarl