判定是否是素数

最normal的方式:
[coolcode lang="C++" linenum="off"]
int is_prime(int n) {
for (int i=2; i<=(int) sqrt(n); i++) if (n%i == 0) return 0;
return 1;
}
void main() {
int i,count=0;
for (i=1; i<10000; i++) count += is_prime(i);
printf("Total of %d primes\n",count);
}
[/coolcode]

改进一点，只要判断到N的开方:
[coolcode lang="C++" linenum="off"]
int is_prime(int n) {
long lim = (int) sqrt(n);
for (int i=2; i<=lim; i++) if (n%i == 0) return 0; return 1;}
[/coolcode]

调用sqrt()方法不够快速，直接用一下代码replace:
用JAVA做测试,下面这个方法在计算100000内质数时,比上面方法快16毫秒。
我的机器性能可能比较低，但是能说明这个算法确实比上面那种快！
[coolcode lang="C++" linenum="off"]
int is_prime(int n) {
for (int i=2; i*i<=n; i++) if (n%i == 0) return 0;
return 1;
}
[/coolcode]

更快一点，我们不用检测偶数因子:
[coolcode lang="C++" linenum="off"]
int is_prime(int n) {
if (n == 1) return 0; // 1 is NOT a prime
if (n == 2) return 1; // 2 is a prime
if (n%2 == 0) return 0; // NO prime is EVEN, except 2
for (int i=3; i*i<=n; i+=2) // start from 3, jump 2 numbers
if (n%i == 0) // no need to check even numbers
return 0;
return 1;
}
[/coolcode]

最高效的算法，列出L和U之间所有素数:
[coolcode lang="C++" linenum="off"]

void sieve(int L,int U) {
int i,j,d;
d=U-L+1; /* from range L to U, we have d=U-L+1 numbers. */
/* use flag[i] to mark whether (L+i) is a prime number or not. */
bool *flag=new bool[d];
for (i=0;ifor (i=(L%2!=0);i/* sieve by prime factors staring from 3 till sqrt(U) */
for (i=3;i<=sqrt(U);i+=2) {
if (i>L && !flag[i-L]) continue;
/* choose the first number to be sieved -- >=L,
divisible by i, and not i itself! */
j=L/i*i; if (jif (j==i) j+=i; /* if j is a prime number, have to start form next
one */
j-=L; /* change j to the index representing j */
for (;j}
if (L<=1) flag[1-L]=false;
if (L<=2) flag[2-L]=true;
for (i=0;icout << endl;
}
[/coolcode]