JAVA经典百题之求100之内的素数

题目：求100之内的素数。

程序分析

求解100以内的素数是一个常见的编程任务。素数是大于1且只能被1和自身整除的整数。我们可以通过遍历每个数，判断其是否为素数来求解100以内的素数。

方法1: 穷举法

解题思路:

• 从2开始遍历每个数，对每个数判断是否为素数，判断方法是看是否能被比它小的数整除。
• 如果不能被任何比它小的数整除，则它是素数。

实现代码:

public class PrimeNumbers {
    public static void findPrimesUsingBruteForce(int limit) {
        System.out.println("Prime numbers up to " + limit + ":");
        for (int i = 2; i <= limit; i++) {
            if (isPrime(i))
                System.out.print(i + " ");
        }
    }

    public static boolean isPrime(int num) {
        if (num < 2)
            return false;

        for (int i = 2; i < num; i++) {
            if (num % i == 0)
                return false;
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

优缺点:

• 优点:
  • 算法简单，容易理解和实现。
• 缺点:
  • 效率较低，时间复杂度为O(n^2)。

方法2: 埃拉托斯特尼筛法

解题思路:

• 初始化一个布尔数组表示每个数是否为素数，初始所有数为素数。
• 从2开始，将所有的倍数标记为非素数。

实现代码:

public class PrimeNumbers {
    public static void sieveOfEratosthenes(int limit) {
        boolean[] isPrime = new boolean[limit + 1];
        for (int i = 0; i <= limit; i++)
            isPrime[i] = true;

        for (int p = 2; p * p <= limit; p++) {
            if (isPrime[p]) {
                for (int i = p * p; i <= limit; i += p)
                    isPrime[i] = false;
            }
        }

        System.out.println("Prime numbers up to " + limit + ":");
        for (int i = 2; i <= limit; i++) {
            if (isPrime[i])
                System.out.print(i + " ");
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

优缺点:

• 优点:
  • 算法效率较高，时间复杂度为O(n log log n)。
• 缺点:
  • 占用较多内存，空间复杂度为O(n)。

方法3: 优化的埃拉托斯特尼筛法

解题思路:

• 优化埃拉托斯特尼筛法，对每个素数的倍数进行标记时，从该素数的平方开始标记，而不是从素数的倍数开始。

实现代码:

public class PrimeNumbers {
    public static void optimizedSieveOfEratosthenes(int limit) {
        boolean[] isPrime = new boolean[limit + 1];
        for (int i = 0; i <= limit; i++)
            isPrime[i] = true;

        for (int p = 2; p * p <= limit; p++) {
            if (isPrime[p]) {
                for (int i = p * p; i <= limit; i += p)
                    isPrime[i] = false;
            }
        }

        System.out.println("Prime numbers up to " + limit + ":");
        for (int i = 2; i <= limit; i++) {
            if (isPrime[i])
                System.out.print(i + " ");
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

优缺点:

• 优点:
  • 算法效率高，时间复杂度为O(n log log n)。
  • 占用较少内存，空间复杂度为O(n)。
• 缺点:
  • 需要理解和实现的优化较多，相对于简单埃拉托斯特尼筛法更复杂。

总结和推荐

• 推荐的方法: 优化的埃拉托斯特尼筛法
• 优化的埃拉托斯特尼筛法综合了效率和空间复杂度的优点，是求解100以内素数的较好选择。
• 穷举法简单但效率低，不适用于大规模数据。
• 埃拉托斯特尼筛法是常用且高效的方法，占用较多内存。
• 优化的埃拉托斯特尼筛法在效率和内存占用上进行了平衡，是常用且推荐的方法。