Java中的质数-算法

Java中的质数-算法

您可以做的是找到的最小除数

Tn

。假设是

p

，再次找到最低的除数

Tn/p

，依此类推。

现在，每一步

p

都是质素的[下面的解释]。因此，请收集它们，它们是的主要除数

Tn

。

为了提高时间复杂度，您最多可以检查除数（最多）

ceil(sqrt(Tn))

，而不是

Tn-1

。

当您开始检查的主要除数时

Tn

，您可以从开始

2

。一旦得到一个主要除数

p

，就不要从

2

for
重新开始

Tn/p

。因为，

Tn/p

同样的除数

Tn

，自

Tn

不必因数小于

p

，

Tn/p

不具备这一点。所以从头开始

p

[

p

可以在

Tn

]中拥有多重力量。如果

p

不分开

Tn

，则移至

p+1

。

范例：

Tn = 45
1.从2开始。2不除以45。2
.下一个测试是针对3. 3被45整除。因此3是其主要除数。
3.现在从45/3 = 15检查素数除数，但从3开始，而不是从2开始。4.好吧，15可以被3整除。所以从15/3 =
5开始。5.注意，ceil（sqrt（5））是3。但是5不能被3整除，但是由于4> ceil（sqrt（ 5）），我们可以毫无疑问地说5是素数。

因此45的素数除数是3和5。

---

为什么数字的最小除数（除1外）是质数？

假设以上陈述为假。那么数字N具有最小的复合除数，例如C。

因此，C | N现在C是合成的，因此除数小于其自身，但大于1。
假设C的这样的因数是P。
所以P | C，但我们有C | N => P | N，其中1 <P <C。

这与我们的假设相反，即C是N的最小除数，因此数的最小除数始终是质数。