# 统计素数
从 0 到某个整数，计算这之间有多少个素数（素数：因子只有 1 和他本身）
# 暴力解法
思路：用过两个 for 循环来判断因子的个数
static int V(int n) { | |
//count 为素数的个数，number 是因子个数 | |
int count = 0; | |
for (int i = 1; i <= n; i++) { | |
int number = 0; | |
for (int j = 2; j < n; j++) { | |
if (i % j == 0) { | |
number += 1; | |
} | |
} | |
if (number == 0 || number == 1) { | |
count += 1; | |
} | |
} | |
return count; | |
} |
# 埃氏筛选法
思路：由于暴力解法中当 n=100 甚至更大的时候，它一定会慢慢从 0 到 n 一个个找，但是没必要找到 n，一个个去找就会出现很多的重复计算，所以，我们可以使用一个标记来标识已经计算过或者可以推导出结果是否是素数的数，就比如标记某个数的倍数，那个倍数的因子一定是大于 2 的。
static int eratosthenes(int n){ | |
boolean[] isPrime = new boolean[n];// 标记 | |
int count = 0;// 记录素数的个数 | |
for(int i =2 ;i <n;i++){ | |
if (!isPrime[i]){ | |
count++; | |
for (int j =i*i;j<n;j+=i){ | |
isPrime[j]=true; | |
} | |
} | |
} | |
return count; | |
} |
有待更新…
