c语言筛选法100以内素数思路
n以内的素数个数不超过？
n以内的素数个数不超过？
直接判断法
int countPrimes(int n) {
int count 0;
for (int i 2; i n; i )
if (isPrim(i)) count ;
return count;
}
// 判断整数 n 是否是素数
boolean isPrime(int n) {
for (int i 2; i n; i )
if (n % i 0)
// 有其他整除因子
return false;
return true;
}
换句话说，如果在 [2,sqrt(n)] 这个区间之内没有发现可整除因子，就可以直接断定 n 是素数了，因为在区间 [sqrt(n),n] 也一定不会发现可整除因子。
使用筛选法：
int countPrimes(int n) {
boolean[] isPrim new boolean[n];
// 将数组都初始化为 true
(isPrim, true);
for (int i 2; i n; i )
if (isPrim[i])
// i 的倍数不可能是素数了
for (int j 2 * i; j n; j i)
isPrim[j] false;
int count 0;
for (int i 2; i n; i )
if (isPrim[i]) count ;
return count;
}
优化，j并不是从2*i开始，而是i*i开始，i也不需要到n，到sqrt(n)即可。
int countPrimes(int n) {
boolean[] isPrim new boolean[n];
(isPrim, true);
for (int i 2; i * i n; i )
if (isPrim[i])
for (int j i * i; j n; j i)
isPrim[j] false;
int count 0;
for (int i 2; i n; i )
if (isPrim[i]) count ;
return count;
}
如何判断一个10位数数字是质数？
最笨的办法——筛选法，依次用质数2 、3 、5 、7、11……分别去除，如果不能整除，即是质数，否则是合数。