C语言中素数的判断方法

介绍三种使用C语言来判断素数的方法，以及用做素数表来判断找素数的方法。

求素数的方法很多，其中最简单的一种就是除以它之前的所有数（从2开始），如果都不能整除，
它就是一个素数。这个是根据素数的定义求解的，只能被1和它本身整除。

但显然这样的效率是不高的，如果要求1-100内的素数，对每一个数除以之前所有的数，有很多优化的余地。
比如除以素数就可以了，没必要去除以合数，于是加一个表，把之前的结果存储下来，利用空间换取时间。

对于素数的判定，其实只需要判定是否能被 sqrt(n) 以内的素数整除。
感性上讲，对于n，要么是质数，只能被1和自己整除，要么能分解质因数，至少有两个素数因子。 n=p..q
因为不可能p和q都大于sqrt(n)（否则乘积就大于n了），所以只需要判断那个小的素数能不能被n整除就可以了。

这样，把求素数的算法又提高了一步，不过计算中大量的用到除法，除法效率一般比较低。
有一种筛法求素数的算法，把1-n排成一排，从2开始，2的倍数肯定不是素数，去除，剩下的数中下一个是3.
再把3的倍数去除，再下一个是5（4已经去除了），以此类推，最后剩下的数必然是素数，因为
它没有被筛，不是任何一个数的倍数（除了1和自己）。这样只需要很多次加法就可以了。
例如一个求 3000000 以内的素数的程序：#include
#include

using namespace std;

const int MAX=3000000;

char table[MAX];
void cal_prime()
{
memset(table, 1, MAX);
for (int i = 2; i < MAX; ++i)
{
if ( table[i] )
{
for ( int j = i+i; j < MAX; j += i )
{
table[j] = 0;
}
}
}
}

int main()
{
clock_t now = clock();
cal_prime();
cout << "execution time :" << clock() - now << endl;;
for ( int i = 2; i < 100; ++i )
{
if ( table[i] )
cout << i << " ";
}
return 0;
}复制代码这算是基本的筛法了，它更是以空间换取时间，因为内存中存的表不只是素数，还有合数的空间，合数比素数多得多。。。
它也有很多优化的余地，比如6，在2的时候筛掉一次。在3的时候又筛掉一次。筛选的时候，一个数之所以能被筛去两次，
它至少是两个质数的倍数，每个质因数筛选一次。通过一定程度上减少重复，可以提升算法的效率。

对于这种算法的改进，有一种更直接的算法，线性筛选，就是对一个合数，就进行一次筛选，极大程度的减少重复计算。

同样条件代码如下：#include
#include

using namespace std;

const int MAX=3000000;

char table[MAX];
int prime[MAX];

int num = 0;

void cal_prime()
{
num = 0;
memset(table, 1, MAX);
for (int i = 2; i < MAX; ++i)
{
if ( table[i] )
prime[num++] = i;
for ( int j = 0; j < num && prime[j] * i < MAX; ++j )
{
table[ prime[j] * i ] = 0;
if ( i % prime[j] == 0 ) break;
}
}
}

int main()
{
clock_t now = clock();
cal_prime();
cout << "execution time :" << clock() - now << endl;;
for ( int i = 2; i < 100; ++i )
{
if ( table[i] )
cout << i << " ";
}
return 0;
}复制代码这个算法又多了两倍的空间存储质数，还好这样空间复杂度也是O(n)。
算法中关键点是
if ( i % prime[j] == 0 ) break;
没有这句这个跟筛法就差不多了，主要是防止重复筛除。

这个应该算是求素数最快的确定性算法了，不过感觉用途也不是非常大，除了学习跟玩之外。。。
一般素数的应用在加密领域，利用一个数分解成两个大素数的积非常难的性质，
数论上大数非常大，数组是不可能放下1-n个数的（寻址都不行了）。这点上这个算法还没有
之前直接除的算法实用，最起码一直等还是能出来结果的。。。

不过在应用的时候可以利用费马小定理试探素数，虽然有一定出错的概率，但是概率非常小，
实际中是能够容忍的。
费马小定理虽然证明是错的，但是总还有不少概率是对的。。。

简单说算法是 判断 2^(n-1) % n == 1 是否成立，成立则基本可认为是素数。（要是整数只能算32以内的素数了，
所以先得有个大整数运算的类，没有写过高效的大整数实现，算法也停留在理论 ⊙﹏⊙b汗。。。）

（
费马定理是 a^(n-1) % n == 1 对所有 a < n 的正整数成立。这个小定理算是逆命题特化，不过
是错的。。。
）

需要自己根据素数的数学定义，自行书写素数判断函数并调用。

1、素数的判断。

根据素数定义，除了1和本身不存在其它约数的正整数为素数。
所以在C语言中判断n是否为素数可以从2开始到到n-1逐一尝试，如果可以整除说明不是素数。
更进一步，可以从2判断到n/2或者n的算术平方根，如果不存在约数，那么即为素数。
除此以外，判断素数的算法还有素数筛等。

2、函数编写：
以遍历判断约数的方法为例，函数可以编写如下：
int isPrime(int n)//判断n是否为素数，如果是则返回1，否则返回0.
{
if(n==1)return 0;//是1直接退出
int i;
for(i = 2; i <= (int)sqrt(n); i ++)//从2到算术平方根遍历。
if(!(n%i)) return 0;//存在约数，不是素数，返回0.
return 1;//不存在约数，返回1，表示为素数。
}
3、以输入一个整数值，判断是否为素数，并输出结果，完整程序如下：

#include
#include
int isPrime(int n)//判断n是否为素数，如果是则返回1，否则返回0.
{
if(n==1)return 0;//是1直接退出
int i;
for(i = 2; i <= (int)sqrt(n); i ++)//从2到算术平方根遍历。
if(!(n%i)) return 0;//存在约数，不是素数，返回0.
return 1;//不存在约数，返回1，表示为素数。
}
int main()
{
int n;
scanf("%d",&n);//输入n值。
if(isPrime(n)) //判断是素数
printf("%d 是素数\n", n);//输出结果。

return 0;
}
注意，用到了平方根函数sqrt,所以需要包含头文件math.h

先来一种比较快速的素数筛选法，这是一种非常高效的筛法，原理的话，你得看下数论方面的书籍#include
#include
#define MAXN 100int flag[MAXN+1];int main()
{
int i,j;
memset(flag,0,sizeof(flag));
for(i=2;i<=MAXN;i++)
{
if(!flag[i])
for(j=i*i;j<=MAXN;j=j+i)
if(!flag[j])
flag[j]=1;
}
for(i=2;i<=MAXN;i++)
if(!flag[i])
printf("%d ",i);
printf("\n");
return 0;
}下面的用的是最普通的算法#include
#include
#define MAXN 100int main()
{
int i,j;
for(i=2;i<=MAXN;i++)
{
if(i==2||i==3||i==5)
printf("%d ",i);
else
{
for(j=2;j<=i;j++)
{
if(i%j==0)
break;
}
if(j==i)
printf("%d ",i);
}
}
printf("\n");
return 0;
}

判断是不是素数，素数就是只能被1和本身整除的自然数。void main()
{ int m,i,k;
printf("please input a number:\n");
scanf("%d",&m);
k=sqrt(m);
for(i=2;iif(m%i==0) break;
if(i>=k)
printf("该数是素数");
else
printf("该数不是素数");
}