我正在尝试解决SPOJ上的一个问题。我们需要计算第n个双胞胎质数对（只差为2的质数）。n可以达到10^5。我尝试使用筛选进行预处理，但需要筛选到10^8才能得到最大的n个双胞胎质数对，但时间限制很严格（2秒），并且超时了。我注意到有人在0.00秒内解决了它，所以我在谷歌上寻找公式，但没有找到任何有用的信息。请问有谁能指导我吗？
提前感谢！
提前感谢！
7个回答
2
我在0.66秒内得到了AC。虽然有0.0秒的解决方案，但我认为可能存在更好的优化方法，因此在这里描述我的方法。
我在“埃拉托斯特尼筛法”中使用了一种基本优化。您知道“2”是唯一的偶数质数，利用这一点可以将计算质数的计算时间和内存减少一半。
其次，所有孪生质数的数字都不会是“2”和“3”的倍数（因为它们是质数！）。因此，这些数字将采用“6N + 1”和“6N + 5”的形式（其余数字肯定不是质数）。 “6N + 5 = 6N + 6-1 = 6（N + 1）-1”。因此，可以看出，对于N> = 1，“6N + 1”和“6N-1”可能是孪生质数。因此，您可以使用之前计算的质数预先计算所有这些值。（平凡情况是3 5）
注意：您无需计算质数直到10 ^ 8，上限要低得多。 [编辑：如果您愿意，我可以分享我的代码，但最好自己想出解决方案。 :) ]
我在“埃拉托斯特尼筛法”中使用了一种基本优化。您知道“2”是唯一的偶数质数，利用这一点可以将计算质数的计算时间和内存减少一半。
其次，所有孪生质数的数字都不会是“2”和“3”的倍数（因为它们是质数！）。因此，这些数字将采用“6N + 1”和“6N + 5”的形式（其余数字肯定不是质数）。 “6N + 5 = 6N + 6-1 = 6（N + 1）-1”。因此，可以看出，对于N> = 1，“6N + 1”和“6N-1”可能是孪生质数。因此，您可以使用之前计算的质数预先计算所有这些值。（平凡情况是3 5）
注意：您无需计算质数直到10 ^ 8，上限要低得多。 [编辑：如果您愿意，我可以分享我的代码，但最好自己想出解决方案。 :) ]
- Priyank Bhatnagar
1
他们的常见问题解答中说，0.00解决方案意味着存在错误。（另外，您有一个打字错误，“6N+6-1 = 6(N + 1)-1”） - Will Ness
2
出于好奇，我使用两个版本的埃拉托斯特尼筛法解决了这个问题。第一个变体在测试机器上完成时间为0.93秒，第二个则为0.24秒。相比之下，在我的电脑上，第一个用时0.08秒，第二个用时0.04秒。
第一个是标准的奇数筛法，第二个是稍微复杂一些的筛法，除了偶数外还省略了3的倍数。
SPOJ的测试机器又旧又慢，因此程序在它们上运行的时间比在典型的最近的计算机上长得多。它们有很小的缓存，因此保持计算量小非常重要。
通过这样做，埃拉托斯特尼筛法足够快。然而，保持内存使用量小真的非常重要。第一个变体每个数字使用一个字节，导致在SPOJ上出现"超时"错误，但在我的计算机上只需要0.12秒。因此，考虑到SPOJ测试机器的特点，使用位筛法可以在规定的时间内解决该问题。
在SPOJ机器上，我通过将筛子的空间减半，获得了显著的加速（运行时间为0.14秒）。由于除了第一对（3,5）之外，所有素数双胞胎都具有形式
如果且仅当 k=5m+4 时，6k+1 可以被 5 整除；如果且仅当 k=5m+1 时，6k-1 可以被 5 整除。因此，5 将标记 5m±1（其中 m≥1）并排除它们成为孪生素数的可能性。同样地，如果且仅当 k=13m+2 时，6k+1 可以被 13 整除；如果且仅当 k=13m-2 时，6k-1 可以被 13 整除。因此，13 将标记 13m±2。这不会改变标记数量，因此对于足够大的缓存，运行时间的变化很小，但对于小缓存来说，这是一个显著的加速。
还有一件事，您的108的限制太高了。我使用了一个更低的限制（2000万），这样就不会高估第100,000个孪生质数对。如果限制为108，第一个变量肯定无法及时完成，第二个可能也不能。
关于您（维基百科的伪代码）的Atkin筛法，有一些注释：
你不需要第二个数组，素数孪生对中较大的一个可以从较小的计算出来。同时，从两个数组中读取数据会浪费空间并破坏缓存本地性。（尽管这与筛选所需时间相比较小。）
现在许多操作系统都限制了栈大小，即使是减小过的限制也会导致立即段错误。栈大小通常被限制为8MB或更小。应该在堆上分配这样大小的数组。
如上所述，每个数字使用一个布尔值会使程序运行比必要的慢得多。您应该使用std::bitset或std::vector或自己编写位操作代码。此外，建议至少省略偶数。
这非常低效。它尝试了太多的x-y组合，对于每个组合，它进行三到四次除法以检查余数模12，并且在数组中来回跳动。
将不同的二次式分开处理。
对于
对于
对于
第一个是标准的奇数筛法，第二个是稍微复杂一些的筛法，除了偶数外还省略了3的倍数。
SPOJ的测试机器又旧又慢，因此程序在它们上运行的时间比在典型的最近的计算机上长得多。它们有很小的缓存，因此保持计算量小非常重要。
通过这样做，埃拉托斯特尼筛法足够快。然而，保持内存使用量小真的非常重要。第一个变体每个数字使用一个字节，导致在SPOJ上出现"超时"错误，但在我的计算机上只需要0.12秒。因此，考虑到SPOJ测试机器的特点，使用位筛法可以在规定的时间内解决该问题。
在SPOJ机器上，我通过将筛子的空间减半，获得了显著的加速（运行时间为0.14秒）。由于除了第一对（3,5）之外，所有素数双胞胎都具有形式
(6*k-1, 6*k+1)，如果k没有产生双胞胎素数对，你也不需要知道这两个数字中哪一个是合数，只需要筛选索引k即可。如果且仅当 k=5m+4 时，6k+1 可以被 5 整除；如果且仅当 k=5m+1 时，6k-1 可以被 5 整除。因此，5 将标记 5m±1（其中 m≥1）并排除它们成为孪生素数的可能性。同样地，如果且仅当 k=13m+2 时，6k+1 可以被 13 整除；如果且仅当 k=13m-2 时，6k-1 可以被 13 整除。因此，13 将标记 13m±2。这不会改变标记数量，因此对于足够大的缓存，运行时间的变化很小，但对于小缓存来说，这是一个显著的加速。
还有一件事，您的108的限制太高了。我使用了一个更低的限制（2000万），这样就不会高估第100,000个孪生质数对。如果限制为108，第一个变量肯定无法及时完成，第二个可能也不能。
通过减少限制，Atkin筛选器需要进行一些优化才能打败省略偶数和3的倍数的Eratosthenes变体，一个天真的实现将明显更慢。
关于您（维基百科的伪代码）的Atkin筛法，有一些注释：
#define limit 100000000
int prime1[MAXN];
int prime2[MAXN];
你不需要第二个数组，素数孪生对中较大的一个可以从较小的计算出来。同时，从两个数组中读取数据会浪费空间并破坏缓存本地性。（尽管这与筛选所需时间相比较小。）
int root = ceil(sqrt(limit));
bool sieve[limit];
现在许多操作系统都限制了栈大小，即使是减小过的限制也会导致立即段错误。栈大小通常被限制为8MB或更小。应该在堆上分配这样大小的数组。
如上所述，每个数字使用一个布尔值会使程序运行比必要的慢得多。您应该使用std::bitset或std::vector或自己编写位操作代码。此外，建议至少省略偶数。
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;
}
}
这非常低效。它尝试了太多的x-y组合，对于每个组合，它进行三到四次除法以检查余数模12，并且在数组中来回跳动。
将不同的二次式分开处理。
对于
4*x^2 + y^2，很明显只需要考虑x < sqrt(limit)/2和奇数的y，然后余数模12是1、5或9。如果余数为9，则4*x^2 + y^2实际上是9的倍数，因此这样的数字会被排除为非平方自由数。然而，最好完全省略筛法中的3的倍数，并单独处理n % 12 == 1和n % 12 == 5的情况。对于
3*x^2 + y^2，很明显只需要考虑x < sqrt(limit/3)，稍加思考就会发现x必须是奇数，y必须是偶数（且不能被3整除）。对于
3*x^2 - y^2，其中 y < x，很明显你只需要考虑 y < sqrt(limit/2)。观察模 12 的余数，可以发现 y 不能被 3 整除，而且 x 和 y 必须有不同的奇偶性。- Daniel Fischer
2
当我在Ideone.com上尝试它时，由于某种原因，基于奇数上的普通vector<bool>的SoE在内存方面比*bitset<N>*表现更好，在小于3200万的速度下相同，在更大的筛大小下甚至比它更快。很容易将找到第n个双子对合并到筛子本身中。 - Will Ness
啊，是的，“vector<bool>”。在大多数实现中，至少我不知道标准是否规定了它，它实际上是一个位向量，就像“UArray Int Bool”一样。我是个C语言程序员（当我不是Haskell程序员时），我总是使用原始数组，这样更简单。 - Daniel Fischer
1
基本上，根据 Wolfram Alpha 的说法，筛选到 20,000,000 就足够了。在 C++ 中使用 Eratosthenes 算法筛选奇数，使用 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秒）。
- Will Ness
0
这里有一个程序可以回答你的问题：
当被3整除时，其商在小数点后第一位为0的质数对称为孪生质数。
这可以写成：
对于任意一对质数Px、Py，如果[ Px/3, 0 ] = [ Py/3, 0 ]，那么Px和Py就是孪生质数。
这个基础是，如果两个质数相差2，那么将所有感兴趣的质数除以3将产生唯一的相等商，当商被修正为小数点后第一位为0时。不相差2的质数将不会在小数点后第一位为0时具有相等的商。
例如：
• 当11、13被3整除时，将产生唯一的商4，当商被修正为小数点后第一位为0时。
• 当17、19被3整除时，将产生唯一的商6，当商被修正为小数点后第一位为0时。
• 当29、31被3整除时，将产生唯一的商10，当商被修正为小数点后第一位为0时。
等等。
以下是使用Excel执行以下操作的简单过程：• 从任何质数列表中查找双子质数 • 在任何质数范围内查找孪生质数 • 查找最大的双子质数 • 查找孪生质数之间的差距
将Kutools导入Excel中。 将感兴趣的质数列在第1列中列出。 在第2列中插入除数3，并向下填充到第1列中最大质数的级别。 将第1列的第一行除以第2列的第一行，并将商放置在第3列中。 将列3向下填充到第1列中最大质数的级别。 校正为零小数。保持选择列3（商）中的数字。 从“条件格式”中，从菜单中选择“重复值” 进入Kutools并选择“到实际”-这将突出显示散布在商列3中的所有孪生对的单元格。 选择第3列中的商号。 在Excel中选择“排序和筛选”。 选择“自定义排序” 在菜单中填写（对于值，选择商标记中的突出显示颜色），然后单击“确定”。 孪生质数将在该列中分组。 然后可以使用此列表查找质数之间的差距。
要找到最大的孪生质数，请使用上述过程，并将已知最大质数的范围输入到第一列中（例如，最高的10k个质数）。
如果在此范围内未找到孪生质数，则继续查找下一个较低的范围，直到找到孪生质数为止。这将是最大的孪生质数。
希望这可以帮助您。
- Eli
0
我使用埃拉托斯特尼筛法预先计算了一大堆质数，然后遍历列表，计算其后继项减2的项目数量，直到找到n个为止。在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;
}
- user448810
3
1这也超时了。2秒时间限制的意思是所有测试用例所花费的时间应该小于2秒。但这个不是。 - frodo
为什么要在列表前面添加元素，然后再反转它，而不是维护尾部并将元素追加到其中？如果你只需要扫描筛子一次，为什么还要构建整个列表呢？而你在构建列表的同时也会进行这个操作。 - Will Ness
SPOJ FAQ 表示
0.0s 的条目是一个 bug。顺便说一下，Ideone 比 SPOJ 快大约 5.5 倍。我们可以以某种方式在源代码中存储预计算的双胞胎，但最少需要 100,000 字节，并且源代码的大小限制为 50K。我想知道这需要多少空间，例如作为哈夫曼编码字符串，这样是否还有足够的空间在源代码中放置解码器？ - Will Ness0
这是我尝试过的。我有一串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;
}
- frodo
2
使用
vector<bool> mark; mark.resize(N+1,true);，它是自动位筛（内存大小的1/8）。不要标记偶数，也不要从中读取。不要构建primesList，而是直接在循环中使用prev_prime辅助变量构建twinprimes。希望这样可以在2秒内运行。如果不能，请使用以下技巧：将mark数组中的第i个条目视为代表数字i而不是2i+1。您的数组将缩小一半。这就是我所做的，它在SPOJ上运行了1.0秒。 - Will Ness如果你真的不知道如何创建一个仅包含奇数的一半大小的数组，可以查看这个链接中的示例：http://stackoverflow.com/questions/10179837/optimization-of-algorithm/10180394#10180394 - Will Ness
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
n个孪生素数的闭式公式，我们将知道它们的数量是有限还是无限。这本身可能值得一枚菲尔兹奖。 - biziclop