计算科学 - 使用 MPI 的连续素数（想要更多关于高效算法的想法） - 吾爱随笔录

计算科学并行计算优化表现高性能计算 mpi

2021-12-15 22:27:36

我是电脑程序编制员。我正在使用 C 语言中的消息传递接口 (MPI)。我执行了一个程序，该程序包括查找从 1 到 10,000,000 的连续素数。

我已经做到了！但我用试除法来做，测试数字的平方根，看看它是否是素数。

例如，要检查一个数字 n，如果它是素数：

int Isprime(int n){

for(i = 2; i <= ceil(sqrt(n)); i++)

{ 
   if(n%i == 0) 
       return 0;
} 

return 1; }

意思是如果一个数 i 小于或等于指定数的平方根，并且 i 除以它，则指定数不是素数。

有人知道更准确的东西吗？我的意思是这样做更有效率？有没有更有效的算法来确定一个数字是否是素数？我忽略了素数的一些重要性质吗？

我的程序的运行时间很好，但我想要更多！:) 想法？

我还想提一下，我不想访问数字列表，因为我的程序不使用主从模型。我没有 MPI_Send 也没有 MPI_Recv。

我也看到了一些关于 Miller-Rabin primalirity test 的东西，但我不明白......

无论如何，想法？

2个回答

我可能在这里说明了显而易见的事情，但是您可以做一些更好的事情...对于初学者，在您的for-loop 中，您可以先检查是否n是偶数，然后开始i=3采取 2 的步骤，例如i += 2. 这可以节省您对所有偶数的测试。

更详细地说，因为你试图找到所有连续的素数，而不是n对所有整数进行测试< sqrt(n)，你最好对所有小于的素数sqrt(n)进行测试。

当然，这有点难以并行化，但成本会随着 $\mathcal O(n/\log n)$ 对比 $\mathcal O(n)$ .

但是，如果您对此很认真，那么您可能应该多阅读一些素数，以至少了解Rabin 测试，因为有比您提出的方法更好的方法可用，即使我已经进行了改进描述。

您实现的算法当然有效，但速度很慢，因为您需要尝试大量长整数除法：每个数字最多为 sqrt(N)。你会发现更好的算法可以让你丢弃几乎所有的候选数 N，而不必在任何关于素数或算法数论的书中进行如此多的除法。我敢肯定，即使是维基百科也有建议。

当然，你可以实现的最简单的算法是 Erathostenes 的筛子，它完全避免了所有的划分。

其它你可能感兴趣的问题