我需要在非常大的数字(在很长的范围内)之间的间隔上测试素数,所以我需要一些快速算法来检查数字是否为素数.请提出您的想法.
你能否建议一种在实践中可用的快速,确定性的方法,用于测试大数是否为素数？
另外,我想知道如何正确使用非确定性素性测试.例如,如果我使用这样的方法,如果输出为"no",我可以确定数字不是素数,但是当输出"可能"时,另一种情况呢？在这种情况下,我是否必须手动测试素数？
提前致谢.
我正在编写一个带有一些素数相关方法的小库.因为我已经完成了基础工作(也就是工作方法),现在我正在寻找一些优化.当然,互联网是一个很好的地方.然而,我偶然发现了一个四舍五入的问题,我想知道如何解决这个问题.
在循环中,我用它来测试一个数字,因为它的搜索效率更高,搜索直到sqrt(n)而不是n/2甚至n - 1.但由于舍入问题,一些数字会被跳过,因此会跳过一些素数!例如,第10000个素数应为:104729,但"优化"版本最终为:103811.
一些代码(我知道,它可以进行更多优化,但我一次只能处理一件事):
/// <summary>
/// Method for testing the primality of a number e.g.: return IsPrime(29);
/// History:
/// 1. Initial version, most basic form of testing: m smaller then n -1
/// 2. Implemented m smaller then sqrt(n), optimization due to prime factoring
/// </summary>
/// <param name="test">Number to be tested on primality</param>
/// <returns>True if the number is prime, false otherwise</returns>
public static bool IsPrime(int test)
{
// 0 and 1 are not prime numbers …想知道如何生成512位(155位十进制数)素数,其中五位十进制数被指定/固定(例如.***28071)？
在没有任何规范的情况下生成简单素数的原则是可以理解的,但我的情况更进一步.
至少,我应该从哪里开始提示？
Java或C#是首选.
谢谢!