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; }