#UVa:10394-Twin Primes

灆洢 2014-12-19 13:04:39

邊建立質數表邊可找出所有的Twin Primes,即可得解。

C++(0.222)

/*******************************************************/
/* UVa 10394 Twin Primes                               */
/* Author: Maplewing [at] knightzone.studio            */
/* Version: 2014/12/19                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

const int PRIME_MAX_LIMIT = 20000000;

int main(){
  vector<bool> prime(PRIME_MAX_LIMIT + 5, true);
  vector<int> twinPrimes;

  prime[0] = false;
  prime[1] = false;
  for( int i = 2 ; i <= PRIME_MAX_LIMIT ; ++i ){
    if( prime[i] ){
      for( int j = i + i ; j <= PRIME_MAX_LIMIT ; j += i ){
        prime[j] = false;
      }
      if( prime[i] && prime[i-2] ){
        twinPrimes.push_back( i-2 );
      }
    }
  }

  int S;
  while( scanf("%d", &S) != EOF ){
    printf("(%d, %d)\n", twinPrimes[S-1], twinPrimes[S-1]+2 );
  }

  return 0;
}

發表迴響

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