hdoj 1262素数ペアを探す
1144 ワード
素数ペアを探す
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 9441 Accepted Submission(s): 4779
Problem Description
ゴッドバッハは皆さんが知っていると思います.私たちは今この結論を証明したいのではなく、プログラム言語の内部で表すことができる数セットで、任意に偶数を取り出して、2つの素数を探して、その偶数に等しくしたいと思っています.
この事実を完成すれば、この推測が成立したことを説明することができる.
同じ偶数を表すために異なる素数対を持つことができるので、探している素数対が2つの値に最も近いことが要求される.
Input
入力は偶数整数M(5
Output
偶数毎に、互いに最も近い2つの素数を出力し、その和は偶数に等しい.
Sample Input
20 30 40
Sample Output
7 13
13 17
17 23
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 9441 Accepted Submission(s): 4779
Problem Description
ゴッドバッハは皆さんが知っていると思います.私たちは今この結論を証明したいのではなく、プログラム言語の内部で表すことができる数セットで、任意に偶数を取り出して、2つの素数を探して、その偶数に等しくしたいと思っています.
この事実を完成すれば、この推測が成立したことを説明することができる.
同じ偶数を表すために異なる素数対を持つことができるので、探している素数対が2つの値に最も近いことが要求される.
Input
入力は偶数整数M(5
Output
偶数毎に、互いに最も近い2つの素数を出力し、その和は偶数に等しい.
Sample Input
20 30 40
Sample Output
7 13
13 17
17 23
#include<stdio.h>
#include<string.h>
#define max 11000
int su[max];
int main()
{
int n,m,j,i,sum;
for(i=1;i<=max;i++)
su[i]=1;
for(i=2;i<=max;i++)
{
if(su[i]==1)
{
for(j=i*i;j<=max;j+=i)
su[j]=0;
}
}
su[1]=0;
while(scanf("%d",&n)!=EOF)
{
sum=0;
for(i=1;i<=n/2;i++)
{
if(su[i]&&su[n-i])
sum=i;
}
printf("%d %d
",sum,n-sum);
}
return 0;
}