#UVa:686-Goldbach’s Conjecture (II)

灆洢 2012-11-29 08:38:42

建質數表,開始從質數表中尋找1~n/2之所有質數p,檢查n-p是否為質數即可。

C++(0.015)

/*******************************************************/
/* UVa 686 Goldbach's Conjecture (II) */
/* Author: LanyiKnight [at] knightzone.studio */
/* Version: 2012/11/29 */
/*******************************************************/
#include <iostream>
#include <cstdio>
using namespace std;

int main(){
  bool composite[33000] = {true,true,false};
  for( int i = 2 ; i < 33000 ; i++ )
    if( !composite[i] )
      for( int j = i+i ; j < 33000 ; j += i )
        composite[j] = true;

  int n, count;
  while( scanf( "%d", &n ) != EOF && n ){

    count = 0;
    for( int i = 2 ; i <= n/2 ; i++ )
      if( !composite[i] && !composite[n-i] ) count++;

    printf( "%d\n", count );
  }
  return 0;
}

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料