Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1966-6ddf6110
この記事にトラックバックする(FC2ブログユーザー)

April 2011 Cook-Off 5問目 - A Prime Conjecture (この記事を編集する[管理者用])

Source

codechef April 2011 Cook-Off 5問目
Problem Statement
codechef April 2011 Cook-Offの参加記録

問題概要

63以上1000000未満の奇数Nが与えられるので,
 N = x + y^2 + z^3
となる素数の組(x,y,z)を1組求める問題.
存在しないなら,それを指摘する.

解法

yとzに関して全探索して,N - y^2 - z^3が素数ならそれをxにしておしまい.
ちなみに,予想は数学的に証明できてないだけで,小さいケースだと全部正しい(つまり解がある)と思うと嵌る.解がないこともある.

C言語のスパゲッティなコード
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define N 1000001
#define ll long long

int getPrime(int n,int p[]){int i,j,n2=n/2;rep(i,n2)p[i]=1;for(i=3;i*i<n;i+=2)if(p[i>>1])for(j=(i*i)>>1;j<n2;j+=i)p[j]=0;j=1;p[0]=2;REP(i,1,n2)if(p[i])p[j++]=i*2+1;return j;}
int ps, p[N];
int res[3], fin;

int prime[N];

int main(){
  int i,j,k,l,m,n;
  long long x, y, z, rest;

  ps = getPrime(N,p);
  rep(i,N) prime[i]=0;
  rep(i,ps) prime[p[i]]=1;

  for(;;){
    scanf("%d",&n); if(!n)break;

    fin = 0; res[0]=res[1]=res[2]=0;
    rep(i,ps){
      x = p[i]*p[i]*p[i]; if(x>n) break;
      rep(j,ps){
        y = x + p[j]*p[j]; if(y>n) break;

        rest = n-y;
        if(!prime[rest]) continue;

        res[0]=rest; res[1]=p[j]; res[2]=p[i];
        fin=1;
        break;
      }
      if(fin) break;
    }

    printf("%d %d %d\n",res[0],res[1],res[2]);
  }

  return 0;
}

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1966-6ddf6110
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。