#UVa:543-Goldbach’s Conjecture

建質數表,從1~n/2都減減看即可得解。

C++(0.055)

/*******************************************************/
/* UVa 543 Goldbach's Conjecture                       */
/* Author: LanyiKnight [at] knightzone.org             */
/* Version: 2012/03/26                                 */
/*******************************************************/
#include<iostream>
#include<cstdio>
using namespace std;

int main(){
  bool composite[1000005] = { true, true };
  bool find;
  int a;

  for( int i = 2 ; i <= 1000000 ; i++ )
    if( !composite[i] )
      for( int j = i+i ; j <= 1000000 ; j += i )
        composite[j] = true;

  int n;
  while( scanf( "%d", &n ) != EOF && n != 0 ){
    find = false;
    for( a = 2 ; a <= n/2 ; a++ )
      if( !composite[a] )
        if( !composite[n-a] ){
          find = true;
          break;
        }
    if( find ) printf( "%d = %d + %d\n", n, a, n-a );
    else printf( "Goldbach's conjecture is wrong.\n" );
  }

  return 0;
}

沒有迴響

本文還沒有迴響,快來搶頭香!

發表迴響