Java 中的半素数

在本教程中，我们将学习 Java 中的半素数。如果一个数 n 可以表示为两个素数的乘积，则称 n 为半素数。在本教程中，我们将探讨如何识别半素数以及如何在给定范围内筛选半素数。

示例 1

输入 6

输出： 是，6 是半素数。

解释： 6 是半素数，因为 6 可以表示为两个素数 2 和 3 的乘积。

示例 2

输入 10

输出： 是，10 是半素数。

解释： 10 是半素数，因为 10 可以表示为两个素数 2 和 5 的乘积。

示例 3

输入 20

输出： 否，20 不是半素数。

解释： 20 不是半素数，因为它不能表示为两个素数的乘积。20 可以表示为 2 x 10，或 4 x 5。在 2 x 10 中，10 不是素数，在 4 x 5 中，4 不是素数。

朴素方法

如果我们进行观察，我们会发现半素数最多有四个因子，其中两个是素数。例如，6 是半素数，因为它有 4 个因子 1、2、3 和 6，其中有两个素数因子 2 和 3。8 不是半素数，因为 8 有 4 个因子 1、2、4 和 8，其中只有一个因子是素数，即数字 2。

为了找到因子，我们可以运行一个从 2 到数字 n 的平方根的循环并计算因子。循环将排除数字本身和 1。之后，我们可以检查计算出的因子是否为素数。如果我们发现任何一个计算出的因子不是素数，我们可以说数字 n 不是半素数。现在是实现部分。

文件名： SemiPrimeNumbers.java

输出

6 is a Semiprime Number.
10 is a Semiprime Number.
20 is not a Semiprime Number.

复杂度分析： 程序的时间复杂度为 O(sqrt(n) x log(log(n)))。程序空间复杂度为 O(1)。

另一种方法

在这个方法中，我们将数字与其除数相除，以去除合数。同时，我们将继续递增变量 cnt，以跟踪素数的计数。

文件名： SemiPrimeNumbers.java

输出

6 is a Semiprime Number.
10 is a Semiprime Number.
20 is not a Semiprime Number.

复杂度分析： 程序的时间复杂度为 O(sqrt(n))。程序空间复杂度为 O(1)。

在给定范围内查找半素数

以下程序说明了如何在一个范围内查找半素数。

文件名： SemiPrimeNumbersRange.java

输出

Semiprime Numbers from 1 to 100 are:
4 6 9 10 14 15 21 22 25 26 33 34 35 38 39 46 49 51 55 57 58 62 65 69 74 77 82 85 86 87 91 93 94 95