土下座しながら探索中

主に競技プログラミング

AOJ 2039 : Space Coconut Crab II

問題リンク:Space Coconut Crab II | Aizu Online Judge

問題概要:
1以上30000以下の整数Tが与えられる
素数3つの和がTとなりそれらの素数を辺とする三角形の数をもとめよ

使用した言語:C++

解法;
あらかじめ30000以下の素数vectorにつめておく
30000以下の素数は3245個なので3重ループでいちいち決めていると厳しい
そこで2重ループで素数を2つ選択したら残りのひとつは T-(1つめの素数 + 2つめの素数)とする
あとはその3つが三角形となっているか判定し、三角形ならカウントしていく

コード:

#include<iostream>
#include<map>
#include<cmath>
#include<vector>
#define MAX 30000
using namespace std;
vector<int> prime;
bool isntprime[30001];
typedef pair<int,int> P;
typedef pair<P,int> Pi;
 
bool isTriangle(int a,int b,int c)
{
  if(a >= b+c || b >= a+c || c >= a+b)
    return false;
  return true;
}
 
int main()
{
  
  isntprime[0] = isntprime[1] = true;
  int j;
  for(int i=2;i<= MAX;i++)if(!isntprime[i])for(prime.push_back(i),j=i*i;j<=MAX;j+=i)isntprime[j] = true;
  
  int T;
  while(cin >> T,T)
    {
      int cnt = 0;
      for(int i=0;i<prime.size() && prime[i] < T;i++)
    for(int j=i;j<prime.size() && prime[i]+prime[j] < T;j++)  
      if(T-(prime[i]+prime[j]) >= prime[j] && !isntprime[T-(prime[i]+prime[j])] && isTriangle(prime[i],prime[j],T-(prime[i]+prime[j])))
        cnt++;
         
      cout << cnt << endl;
    }
  return 0;
}