判断是否为素数

需求描述

Write a Java Program to find whether a number is prime or not.

解决方案

方法一：使用传统的方法来检查一个数是否为素数

public class Main {
    public static void main(String[] args) {
        int num = 29;
        boolean flag = false;
        for(int i = 2; i <= num/2; ++i)
        {
            // 条件为真，则 num 不是素数
            if(num % i == 0)
            {
                flag = true;
                break;
            }
        }

        if (!flag)
            System.out.println(num + " 是一个素数。");
        else
            System.out.println(num + " 不是一个素数。");
    }
}

解释：
在这段代码中，我们首先定义一个标志变量 flag，并将其初始值设为 false。然后，我们使用 for 循环从 2 遍历到 num/2。在每次迭代中，我们检查 num 是否可以被 i 整除。如果 num 可以被任何 i 整除，那么我们就设置 flag 为 true，并退出循环。最后，如果 flag 仍然为 false，那么 num 就是一个素数。

时间复杂度：这个算法的时间复杂度为 O(n)，其中 n 是输入数字的一半。

空间复杂度：这个算法的空间复杂度为 O(1)，因为我们只使用了一些固定大小的变量。

方法二：使用优化的方法来检查一个数是否为素数

public class Main {
    public static void main(String[] args) {
        int num = 29;
        boolean flag = false;
        for(int i = 2; i <= Math.sqrt(num); ++i)
        {
            // 条件为真，则 num 不是素数
            if(num % i == 0)
            {
                flag = true;
                break;
            }
        }

        if (!flag)
            System.out.println(num + " 是一个素数。");
        else
            System.out.println(num + " 不是一个素数。");
    }
}

解释：
这个优化的算法基于一个事实，那就是一个合数必定有一个小于或等于它平方根的因数。所以，我们只需要检查从 2 到 √num 的数字是否可以整除 num。这样就可以大大减少检查的次数。

时间复杂度：这个算法的时间复杂度为 O(√n)，其中 n 是输入数字的平方根。

空间复杂度：这个算法的空间复杂度为 O(1)，因为我们只使用了一些固定大小的变量。