判断素数法
1、穷举判断法1:从2到n-1判断有没有能整除n的数。如果有，则不是素数，否则，是素数。
如下示例程序:
int _prime(int n)
{
if (n < 2)
{
return 0;
}
int i;
for (i = 2; i < n; i++)
{
if (n%i == 0)
{
return 0;
}
}
return 1;
}
2、穷举判断法2:在上列程序的的基础上进行改进，从2一直算到sqrt(n)，这样算法复杂度降低了很多。
如下示例程序:
int_prime(int n)
{
if (n < 2)
{
return 0;
}
int i;
for (i = 2; i*i <= n; i++)
{
if (n%i == 0)
{
return 0;
}
}
return 1;
}
判断一个数的范围里有多少个素数
1、Eratosthenes筛法:早在2000年前人们就知道了一个不必用除法而找出2~N的所有质数的方法。假设一个很神奇的筛子，可以给出一个数，例如i，这个筛子有办法把i所有的倍数去掉。请用这个方法求出2~N之间的所有质数。即Eratosthenes筛选法。
如下示例程序:
#define N 1000
char flag[N];
void fun()
{
long long i, j;
for (i = 0; i < N; i++)
{
flag[i] = 1;
}
flag[0] = flag[1] = 0;
for (i = 2; i < N; i++)
{
if (!flag[i]) continue;
for (j = i*i; j < N; j += i)
{
flag[j] = 0;
}
}
}
如上数组,下标为判断的数，如这个数组[下标] = 1则下标代表的数为素数，这种方法大大减少了运算量，提高了计算机的运算效率。