优草派  >   Python

求0到100内的素数

李嘉琪            来源:优草派

素数是指只能被1和它本身整除的数,是数学中一个重要的概念。在0到100的范围内,有许多素数,本文将从多个角度分析如何求出这些素数。

求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),比其他两种方法都要快得多。

【原创声明】凡注明“来源:优草派”的文章,系本站原创,任何单位或个人未经本站书面授权不得转载、链接、转贴或以其他方式复制发表。否则,本站将依法追究其法律责任。
TOP 10
  • 周排行
  • 月排行