私はSPOJの問題を解決しようとしていました。n番目の双子素数ペア（2だけ異なる素数）を計算する必要があります。nは10^5まで大きくすることができます。ふるいを使って事前計算を試みました。最大のn双子素数を得るには、最大10 ^ 8のふるいをかける必要がありましたが、制限時間は厳密（2秒）でタイムアウトになります。人々が0.00秒でそれを解決したことに気づいたので、私はグーグルで数式を探しましたが、何も役に立ちませんでした。誰かが私を案内してくれませんか？
前もって感謝します！！
質問する
3956 次
7 に答える
2
私は0.66秒でACを取得しました。0.0sのソリューションがあるので、より良い最適化が可能であると思いますが、ここで私のアプローチを説明します。
で1つの基本的な最適化を使用しましたSieve of Eratosthenes。これが唯一の素数であることがわかってい2ます。これを使用すると、素数を計算するための計算時間とメモリを半分に減らすことができます。
第二に、双子素数であるすべての数はとの倍数では2ありません3（それらは素数であるため！）。したがって、これらの数はとの形式6N+1になります6N+5（残りは確かに素数ではありません）。6N+5 = 6N+6-1 = 6(N+1)-1。したがって、> = 1の場合、双子素数6N+1に6N-1なる可能性があることがNわかります。したがって、前に計算した素数を使用して、これらすべての値を事前に計算します。（重要なケースは3 5です）
注：10^8まで素数を計算する必要はありません。上限ははるかに低くなります。[編集：必要に応じてコードを共有できますが、自分で解決策を考え出す方がよいでしょう。:)]
于 2012-04-13T22:19:39.523 に答える
2
好奇心から、エラトステネスのふるいの2つのバリエーションを使用して問題を解決しました。最初のバリアントは0.93秒でテストマシンで完了し、2番目のバリアントは0.24秒で完了しました。比較のために、私のコンピューターでは、最初のコンピューターは0.08秒で終了し、2番目のコンピューターは0.04秒で終了しました。
1つ目は奇数の標準ふるいで、2つ目は偶数に加えて3の倍数も省略したもう少し手の込んだふるいです。
SPOJのテストマシンは古くて遅いので、プログラムは通常の最近のボックスよりもはるかに長く実行されます。また、キャッシュが小さいため、計算を小さく保つことが重要です。
そうすることで、エラトステネスのふるいは簡単に十分に速くなります。ただし、メモリ使用量を少なく保つことが非常に重要です。数値ごとに1バイトを使用する最初のバリアントは、SPOJで「制限時間を超えました」を示しましたが、私のボックスでは0.12秒で実行されました。したがって、SPOJ試験機の特性を考慮して、ビットふるいを使用して、指定された時間内にそれを解決します。
SPOJマシンでは、ふるいのスペースをさらに半分に減らすことで、大幅なスピードアップ（実行時間0.14秒）が得られました。-最初のペア（3,5）を除いて-すべての素数の形(6*k-1, 6*k+1)はであり、双子素数のペアが生成されない場合は、2つの数のどちらが合成数であるかを知る必要がないkため、ふるいにかけるだけで十分です。インデックスk。
（一部の6*k + 1場合に限り5で割り切れ、k = 5*m + 4一部の場合に限り5で割り切れるので、5は双子素数を生成しないとマークされます。同様に、一部の場合に限り13で割り切れます。一部の場合に限り、13はマークオフします。）m6*k - 1k = 5*m+1m5*m ± 1, m >= 16*k+1k = 13*m + 2m6*k - 1k = 13*m - 2m13*m ± 2
これはマーキングの数を変更しないため、キャッシュが十分に大きい場合、実行時間の変化はわずかですが、キャッシュが小さい場合は大幅に高速化されます。
ただし、もう1つ。108の制限は高すぎます。私は、10万番目の双子素数ペアをそれほど過大評価しない下限（2000万）を使用しました。10 8の制限がある場合、最初のバリアントは確かに時間内に終了しませんでしたが、2番目のバリアントはおそらく時間内に終了しませんでした。
制限が減ったため、Eratosthenesバリアントを打ち負かすためにSieve of Atkinをある程度最適化する必要があり、偶数と3の倍数を省略して、単純な実装は大幅に遅くなります。
あなたの（ウィキペディアの擬似コード）アトキンのふるいに関するいくつかの意見：
#define limit 100000000
int prime1[MAXN];
int prime2[MAXN];
2番目の配列は必要ありません。プライムツインペアの大きい方のパートナーは、小さい方から簡単に計算できます。スペースを浪費し、2つのアレイからのキャッシュの局所性の読み取りを破棄しています。（ただし、ふるい分けに必要な時間と比較すると、それはマイナーです。）
int root = ceil(sqrt(limit));
bool sieve[limit];
最近の多くのオペレーティングシステムでは、制限が緩和されていても、これは瞬時のセグメンテーション違反です。多くの場合、スタックサイズは8MB以下に制限されています。そのサイズの配列はヒープに割り当てる必要があります。
上記のように、bool数値ごとに1つを使用すると、プログラムの実行が必要以上に遅くなります。std::bitsetまたはまたはstd::vector<bool>またはビットを自分でいじる必要があります。また、少なくとも偶数を省略することをお勧めします。
for (int x = 1; x <= root; x++)
{
for (int y = 1; y <= root; y++)
{
//Main part of Sieve of Atkin
int n = (4*x*x)+(y*y);
if (n <= limit && (n % 12 == 1 || n % 12 == 5)) sieve[n] ^= true;
n = (3*x*x)+(y*y);
if (n <= limit && n % 12 == 7) sieve[n] ^= true;
n = (3*x*x)-(y*y);
if (x > y && n <= limit && n % 12 == 11) sieve[n] ^= true;
}
}
これはひどく非効率的です。非常に多くのxyの組み合わせを試行します。組み合わせごとに、12を法とする余りをチェックするために3つまたは4つの除算を実行し、配列内を前後にホップします。
異なる二次方程式を分離します。
の場合、考慮すれ4*x^2 + y^2ばよいのは明らかです。その場合、12を法とする剰余は1、5、または9です。剰余が9の場合、実際には9の倍数であるため、このような数は平方フリーではないため削除されます。ただし、ふるいから3の倍数を完全に省略し、ケースを個別に処理することをお勧めします。x < sqrt(limit)/2y4*x^2 + y^2n % 12 == 1n % 12 == 5
の場合3*x^2 + y^2、考慮する必要があるx < sqrt(limit/3)のは明らかであり、少し考えれば、それはx奇数で偶数でなければならないことがわかりますy（3で割り切れないようにする必要があります）。
3*x^2 - y^2withの場合y < x、考慮する必要があるのは明らかですy < sqrt(limit/2)。12を法とする余りを見ると、y3で割り切れてはならず、異なるパリティを持っている必要があることがわかります。xy
于 2012-04-14T00:30:24.300 に答える
1
したがって、Wolfram Alphaによると、基本的には最大20,000,000のふるい分けで十分です。C ++でエラトステネスのプレーンシーブを使用しvector<bool>ます（ところで、どの言語を使用していましたか？）。
ふるいループのすぐ内側で双子素数を追跡します。双子を見つけたら、ペアの下の素数を別のベクトルに格納します。順序が正しくない（前よりも小さい）インデックスが要求された場合（説明ページに示されている例とは異なります）、このストレージからプライムを取得します。
size_t n = 10000000, itop=2236;
vector<bool> s;
vector<int> twins;
s.resize(n, true);
int cnt, k1, k2, p1=3, p2, k=0;
cin >> cnt;
if( cnt-- > 0 )
{
cin >> k1;
for( size_t i=1; i < n; ++i ) // p=2i+1
{
if( s[i] )
{
p2 = 2*i+1;
if( p2-p1 == 2 ) { ++k; twins.push_back(p1); }
if( k==k1 )
{
cout << p1 << " " << p2 << endl;
......
など。1.05秒（Ideoneでは0.18秒）で受け入れられました。または、ロジックを解きほぐします。すぐに100,000の双子素数ペアを事前に計算し、後で別のループでそれらにアクセスします（0.94秒）。
于 2012-04-16T02:12:59.710 に答える
1
これを解決するための効率的なアルゴリズムの説明は、@ Programming Praxisのエントリにあります。また、SchemeとPerlのサンプルコードも提供されています。
于 2012-04-18T12:00:22.563 に答える
0
これは私が試みたものです。TLEの文字列があります。
bool mark [N];
vector <int> primeList;
void sieve ()
{
memset (mark, true, sizeof (mark));
mark [0] = mark [1] = false;
for ( int i = 4; i < N; i += 2 )
mark [i] = false;
for ( int i = 3; i * i <= N; i++ )
{
if ( mark [i] )
{
for ( int j = i * i; j < N; j += 2 * i )
mark [j] = false;
}
}
primeList.clear ();
primeList.push_back (2);
for ( int i = 3; i < N; i += 2 )
{
if ( mark [i] )
primeList.push_back (i);
}
//printf ("%d\n", primeList.size ());
}
int main ()
{
sieve ();
vector <int> twinPrime;
for ( size_t i = 1; i < primeList.size (); i++ )
{
if ( primeList [i] - primeList [i - 1] == 2 )
twinPrime.push_back (primeList [i - 1]);
}
int t;
scanf("%d",&t);
int s;
while ( t-- )
{
scanf("%d",&s);
printf ("%d %d\n", twinPrime [s - 1], twinPrime [s - 1] + 2);
}
return 0;
}
于 2012-04-17T12:36:31.693 に答える
0
私はエラトステネスのふるいを使用して素数の大規模なリストを事前に計算し、次にそれらのn個が見つかるまで、後継者より2少ないアイテムを数えるリストを繰り返しました。http://ideone.com/vYjuCで1.42秒で実行されます。私もゼロ秒で答えを計算する方法を知りたいです。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ISBITSET(x, i) (( x[i>>3] & (1<<(i&7)) ) != 0)
#define SETBIT(x, i) x[i>>3] |= (1<<(i&7));
#define CLEARBIT(x, i) x[i>>3] &= (1<<(i&7)) ^ 0xFF;
typedef struct list {
int data;
struct list *next;
} List;
List *insert(int data, List *next)
{
List *new;
new = malloc(sizeof(List));
new->data = data;
new->next = next;
return new;
}
List *reverse(List *list) {
List *new = NULL;
List *next;
while (list != NULL)
{
next = list->next;
list->next = new;
new = list;
list = next;
}
return new;
}
int length(List *xs)
{
int len = 0;
while (xs != NULL)
{
len += 1;
xs = xs->next;
}
return len;
}
List *primes(int n)
{
int m = (n-1) / 2;
char b[m/8+1];
int i = 0;
int p = 3;
List *ps = NULL;
int j;
ps = insert(2, ps);
memset(b, 255, sizeof(b));
while (p*p < n)
{
if (ISBITSET(b,i))
{
ps = insert(p, ps);
j = (p*p - 3) / 2;
while (j < m)
{
CLEARBIT(b, j);
j += p;
}
}
i += 1; p += 2;
}
while (i < m)
{
if (ISBITSET(b,i))
{
ps = insert(p, ps);
}
i += 1; p += 2;
}
return reverse(ps);
}
int nth_twin(int n, List *ps)
{
while (ps->next != NULL)
{
if (n == 0)
{
return ps->data - 1;
}
if (ps->next->data - ps->data == 2)
{
--n;
}
ps = ps->next;
}
return 0;
}
int main(int argc, char *argv[])
{
List *ps = primes(100000000);
printf("%d\n", nth_twin(100000, ps));
return 0;
}
于 2012-04-13T18:15:16.783 に答える
0
これがあなたの質問に答えることができる手順です：
3で割ったときに、10進数の0（ゼロ）に修正されたときに等しい商を持つ素数は、双子素数です。
これは次のように書くことができます
素数Px、Pyの任意のペアについて、[Px / 3、0] = [Py / 3、0]の場合、PxとPyは素数双子です。
これの根拠は、素数が2だけ異なる場合、対象のすべての素数を除算すると、商が10進数のゼロに修正されたときに一意の等しい商が生成されるということです。2で区切られていない素数は、小数ゼロに修正されたときに等しい商を持ちません。
例えば：
•11、13を3で割ると、商が10進数のゼロに修正されたときに、一意の4の商が生成されます。
•17、19を3で割ると、商が10進数のゼロに修正されたときに6の一意の商が生成されます。
•29、31を3で割ると、商が10進数のゼロに修正されたときに10の一意の商が生成されます。
等。
以下は、Excelを使用した簡単な手順です。
•任意の素数のリストから双子素数を検索します•任意の範囲の素数で双子素数を検索します•最大の素数双子素数を検索します•双子素数間のギャップを検索します
- KutoolsをExcelにインポートする
- 関心のある素数を列1にリストします。
- 列2に除数3を挿入します-列1のリストで最大の素数のレベルまで入力します。
- 列1の最初の行を列2の最初の行で除算し、商を列3に配置します
- 列3を、列1のリストで最大の素数のレベルまで入力します。
- 小数点以下ゼロに修正します。数字の列3（商）を選択したままにします。
- 「条件付き書式」から-メニューから「値の重複」を選択します
- Kutoolsに移動し、「toactual」を選択します-これにより、商列3に散在するすべてのツインペアのセルが強調表示されます。
- 列3の商を選択します
- Excelで[並べ替えとフィルター]を選択します
- 「カスタムソート」を選択します
- メニューに入力し（値については、商の列で強調表示された色を選択します）、[OK]をクリックします。
- 双子素数は列にグループ化されます。このリストを使用して、素数間のギャップを見つけることができます。
最大の双子素数を見つけるには、上記の手順を使用して、既知の最大の素数の範囲を列1に入れます（たとえば、最高の10k素数）。
この範囲で双子素数が見つからない場合は、双子素数が見つかるまで次に低い範囲に移動します。これは最大の双子素数になります。
お役に立てれば。
于 2017-08-15T14:56:01.147 に答える