素数是指只能被1和它本身整除的数,是数学中一个重要的概念。在0到100的范围内,有许多素数,本文将从多个角度分析如何求出这些素数。
一、暴力枚举法
最简单的方法就是暴力枚举法,即从2开始,依次判断每个数是否是素数。具体实现方法如下:
```
for (int i = 2; i <= 100; i++) {
boolean isPrime = true;
for (int j = 2; j < i; j++) {
if (i % j == 0) {
isPrime = false;
break;
}
}
if (isPrime) {
System.out.println(i);
}
}
```
这段代码依次判断2到100之间的每个数是否是素数,如果是素数就输出它。对于每个数,我们都需要从2到它本身-1依次判断是否能整除,这样的时间复杂度为O(n^2),不够高效。
二、埃氏筛法
埃氏筛法(Sieve of Eratosthenes)是一种较为高效的素数筛法,具体思路如下:
1. 先把1到100的整数写出来;
2. 从2开始,把每个素数的倍数都标记成合数,即把2的倍数、3的倍数……都标记成合数(除了2本身和3本身);
3. 找到下一个未被标记的数,它就是素数,然后把它的倍数都标记成合数;
4. 重复步骤3,直到找到100以内的所有素数。
具体实现方法如下:
```
boolean[] isPrime = new boolean[101];
Arrays.fill(isPrime, true);
for (int i = 2; i <= 100; i++) {
if (isPrime[i]) {
System.out.println(i);
for (int j = 2 * i; j <= 100; j += i) {
isPrime[j] = false;
}
}
}
```
这段代码首先把1到100之间的所有数都标记为素数(即isPrime数组的所有元素都为true),然后从2开始依次判断每个数是否是素数。如果是素数,就输出它,并把它的倍数都标记为合数(即把isPrime[j]设为false)。这样就能找到100以内的所有素数。
埃氏筛法的时间复杂度为O(nloglogn),比暴力枚举法要高效很多。
三、欧拉筛法
欧拉筛法(Sieve of Euler)是一种更加高效的素数筛法,它结合了埃氏筛法和线性筛法的优点。
具体思路如下:
1. 把1到100的整数写出来;
2. 从2开始,依次枚举每个数,如果它是素数,就把它存入素数数组prime中;
3. 对于每个数x,如果它是素数,就把它的倍数都标记成合数,但不标记重复的数;
4. 重复步骤2和步骤3,直到找到100以内的所有素数。
具体实现方法如下:
```
int[] prime = new int[101];
boolean[] isPrime = new boolean[101];
int cnt = 0;
Arrays.fill(isPrime, true);
for (int i = 2; i <= 100; i++) {
if (isPrime[i]) {
prime[cnt++] = i;
}
for (int j = 0; j < cnt && i * prime[j] <= 100; j++) {
isPrime[i * prime[j]] = false;
if (i % prime[j] == 0) {
break;
}
}
}
for (int i = 0; i < cnt; i++) {
System.out.println(prime[i]);
}
```
这段代码首先定义一个素数数组prime和一个布尔数组isPrime,然后从2开始依次判断每个数是否是素数。如果是素数,就把它存入素数数组prime中,并把它的倍数都标记为合数。对于每个数x,我们只需要枚举素数数组prime中小于等于sqrt(x)的数,就能标记x的倍数为合数。因为如果x有一个大于sqrt(x)的因数,那么它一定有一个小于sqrt(x)的因数。
欧拉筛法的时间复杂度为O(n),比埃氏筛法还要高效。
综上所述,我们可以用暴力枚举法、埃氏筛法和欧拉筛法来求0到100内的素数。其中,欧拉筛法是最高效的方法,它的时间复杂度为O(n),比其他两种方法都要快得多。