如何测试1000位数的素数？
我试图找到数字是否为1000或更长的素数。 我想使用的算法是6k +/- 1
我面临的问题是如何在java中存储这么长的数字，它是以字符串作为输入。
要么
为了做到可分性，应该只考虑数字的最后几位数。
请指教
如果足以确定数字是否为PROBABLY prime，则可以使用内置的isProbablePrime函数
- 如果调用返回true，则该数字为素数的概率超过（1 – 1 /（2 ^确定性））。
- 如果调用返回false，则该数字肯定不是素数。
你应该在2和3号基地使用Lucas pseudoprime测试和Rabin-Miller强伪测试 。如果所有三个都给出了可能是素数的结果，那么出于所有实际原因你应该考虑它。 此测试没有已知的反例。 如果你必须生成素数证书，那么你可以使用椭圆曲线素数certificate器 ，但它会非常慢。
如果需要在32/64位空间之外处理整数，则应使用BigInteger 。 不知道你需要担心的是否存在实际限制。
的BigInteger
6k +/- 1不是素性测试！ 如果你已经知道Q是素数（并且大于7），那么知道它是6k +/- 1的forms告诉你它是否“安全” – Q + 1和Q-1都有很大的因素，使Q更难以因素（因此对于加密目的而言“安全”）。 但是6k +/- 1forms的大多数数字都是复合数。
来自维基百科的“Safe Prime”页面
如果想编写自己的例程来测试1000位数字的素数，你会想要像其他答案所建议的那样使用BigInteger类。 你可以先使用费马测试，它会告诉你这个数字是“绝对复合”还是“可能是素数”。 然后，您可以使用像Miller-Rabin或Solovay-Strassen这样的计算密集型测试，对最终确定性测试的“可能是素数”数字进行测试。
来自维基百科的Primality测试算法
1000位数字使用BigDecimal少于350字节的内存。 你会发现你可以处理比这大得多的数字。
你会发现的问题是你需要检查很多数字，大约10 ^ 31这需要很长时间，大约10 ^ 18年。
如果您不喜欢概率方法，也可以使用确定性多项式算法 。
但是，除非神灵正在冒险并拉扯你的腿或什么东西，你应该只使用更快的概率方法。
你可以使用一些想法。
- 算法6k +/- 1
- 检查直到除数小于sqrt（素数）
- 检查仅按素数划分
结合这些方法，您可以加快validation速度。
此链接可以帮助您： http ： //www.osix.net/modules/article/？id = 791
当然还要使用BigInteger。
如果你不是在寻找一种可编程的方法，你应该问一下wolframalpha
fx：“是1754179634151752538176965974334085811645204614256364837827967一个素数”
返回：“1754179634151752538176965974334085811645204614256364837827967是一个素数！”