[Swust OJ 610]--吉祥数
5989 ワード
タイトルリンク:http://acm.swust.edu.cn/problem/610/
Time limit(ms): 1000 Memory limit(kb): 65535
Description
すぐ新年で、ここで早めにみんなの新年の楽しみを祈って、まずみんなに1つの吉祥数--1898を送ります.意味は分かると思いますが、次のヒントに基づいて、私たちの吉祥数に関する数を見つけてください.
2008以下のすべての素数を小さいものから大きいものまで1行目に並べてください.2行目の各数は、頭の素数と右肩の素数の差に等しいです.プログラミングは、2行目の数にこのようないくつかの連続的な整数が存在するかどうかを求め、それらの和はちょうど1898ですか?偽好が存在するなら、またいくつかのこのような状況がありますか?例:
1行目:2 3 5 7 11 17・・・1979 1987 1993
2行目:1 2 2 4 4...8 6
Input
入力なし
Output
複数の結果を出力し、すべての条件を満たす結果を出力し、各結果に対応する1行目の開始数と終了数のみを出力することを要求し、2つの数の間に2つの格子が空き、各結果の間に改行し、すべての結果は開始数が大きい順から小さい順に出力する.具体的にはSampleを参照
Sample Input
入力なし
Sample Output
101 1999
89 1987
……
……
……
解題構想:(1)第1行の素数をn[1]、n[2]、n[3]と仮定する.n、...2行目の差はm[1]、m[2]、m[3]...m[j]....ここで、m[j]は、m[j]=n[j+1]−n[j]である.
(2)第2行連続N個数の和は、
SUM=m[1]+m[2]+m[3]+...+m[j]
=(n[2]-n[1])+(n[3]-n[2])+(n[4]-n[3])+...+(n[j+1]-n[j])
=n[j+1]-n[1]
これにより,2008を超えないすべての素数にこのような2つの素数が存在するかどうか,それらの差はちょうど1898である.存在する場合、2行目には必ず必要な整数シーケンスがあり、その和は1898です.
等価問題の解は比較的簡単である.
解析から,素数シーケンスに2を含める必要はなく,任意の素数と2の差は必ず奇数であるため,考慮する必要はないことが分かった.(同じ素数は素数表で表を打つことで得られる)
コードは次のとおりです.
1 #include <iostream>
2 #include <cstring>
3 using namespace std;
4 int ptr[520], prime[2015] = { 0, 0, 1 };
5 void init(){
6 int i, j;
7 memset(prime, 1, sizeof(prime));
8 for (i = 2; i <= 2008; i++){
9 if (prime[i]){
10 for (j = 2; i*j <= 2008; j++)
11 prime[i*j] = 0;
12 }
13 }
14 }
15 int main(){
16 int i, j;
17 init();
18 for (j = 0, i = 3; i <= 2008; i += 2)
19 if (prime[i])
20 ptr[j++] = i;
21 for (j--; ptr[j] > 1898; j--){
22 for (i = 0; ptr[j] - ptr[i] > 1898; i++);
23 if (ptr[j] - ptr[i] == 1898)
24 cout << ptr[i] << " " << ptr[j] << endl;
25 }
26 return 0;
27 }View Code