Java 中的 Giuga 数

Giuga 数是一个复合数 N，它有一个独特的性质。该性质规定，对于 N 的每个素数因子 p，N 除以 p 减 1 ((N/p) - 1) 也必须能被 p 整除。如果一个数 N 对其所有素数因子都满足此条件，则它被认为是 Giuga 数。

要检查给定的数 N 是否为 Giuga 数，您需要验证其所有素数因子的此项性质。如果对每个素数因子都成立，则数 N 被归类为 Giuga 数，输出为“是”。如果该性质对其素数因子不成立，则该数不是 Giuga 数，结果为“否”。

以下是一些进一步的示例，用于说明 Giuga 数的概念

示例 1

输入： N = 24

输出： 否

解释

24 是一个复合数，其素数因子为 {2, 3}。

2 不能整除 24 / 2 - 1 = 11，并且

3 不能整除 24 / 3 - 1 = 7。

示例 2

输入： N = 56

输出： 否

解释

56 是一个复合数，其素数因子为 {2, 7}。

2 不能整除 56 / 2 - 1 = 27

7 能整除 56 / 7 - 1 = 7。

示例 3

输入： N = 49

输出： 否

解释

49 是一个复合数，其素数因子为 {7}。

7 不能整除 49 / 7 - 1 = 6

示例 4

输入： N = 30

输出： 是

解释

30 是一个复合数，其素数因子为 {2, 3, 5}。

2 能整除 30 / 2 - 1 = 14，

3 能整除 30 / 3 - 1 = 9，

5 能整除 30 / 5 - 1 = 5。

方法：暴力枚举法

在此方法中，代码会迭代从 2 到 (N-1) 的所有数字，以检查每个 i 是否满足 Giuga 数的性质。它检查每个 i 是否为素数，N 是否能被 i 整除，以及 (N/i - 1) 是否能被 i 整除。如果所有条件至少对一个 i 成立，则该数 N 不被视为 Giuga 数。如果找不到这样的 i，则 N 被视为 Giuga 数。

算法

步骤 1： 创建一个名为 isPrime(number) 的方法，用于确定给定的数字是否为素数。

步骤 2： 当给定的数字小于或等于 1 时，返回 false，因为此范围内的数字不被视为素数。

步骤 3： 从 2 迭代到给定数字的平方根

1. 如果数字在此范围内的任何整数可整除，则立即返回 false，表明它不是素数。

步骤 4： 当循环中未找到任何除数时，返回 true，表明该整数是素数。

步骤 5： 创建一个 isGiugaNumber(n) 方法来检查给定的数字是否为 Giuga 数。

步骤 6： 如果输入的数字是素数，则返回 false，因为素数不可能是 Giuga 数。

步骤 7： 迭代从 2 到输入数字减一的整数

1. 对于每个整数 i，使用 isPrime(i) 方法检查它是否为素数。
2. 检查输入的数字 n 是否能被 i 整除。
3. 检查 (n / i - 1) 是否能被 i 整除。
4. 如果所有条件都满足，则返回 true，表示这是一个 Giuga 数。

步骤 8： 如果找不到任何打破 Giuga 数性质的 i，则返回 false，表示该数字不满足 Giuga 数的性质。

实施

文件名： GiugaNumberChecker.java

输出

30 is a Giuga number.

时间复杂度： O(n²)，其中 n 是输入数字。

空间复杂度： O(1)