概念：
素数又称质数。指在一个大于1的自然数中，除了1和此整数自身外，没法被其他自然数整除的数，素数个数是无穷的。换句话说，只有两个正因数（1和自己）的自然数即为素数。比1大但不是素数的数称为合数。1和0既非素数也非合数。合数是由若干个质数相乘而得到的。所以，质数是合数的基础，没有质数就没有合数。这也说明了前面所提到的质数在数论中有着重要地位。历史上曾将1也包含在质数之内，但后来为了算术基本定理，最终1被数学家排除在质数之外，而从高等代数的角度来看，1是乘法单位元，也不能算在质数之内，并且，所有的合数都可由若干个质数相乘而得到。
判断素数的算法(源码)：
View Code
1 /**********************************************************************************
2 * Copyright(c)2011-2011 Company Name:ChengDu University of Information Technology
3 * All rights not reserved
4 *
5 * 文件名称: IsPrime.cpp
6 * 文件说明: 构造素数数列
7 *
8 * 完成日期: 2011.9.15
9 * 当前版本: v1.0
10 *
11 * 算法说明:
12 * 例如:11%3 != 0可以确定11%(3*i) != 0.
13 * 定理: 如果n不是素数, 则n有满足1<d<=sqrt(n)的一个"素数"因子d.
14 * 证明:
15 * 1. 如果n不是素数, 则n有满足1<d<=sqrt(n)的一个因子d.
16 * 2. 如果d是素数, 则定理得证, 算法终止.
17 * 3. 令n=d, 并转到步骤1.
18 * 由于不可能无限分解n的因子, 因此上述证明的算法最终会停止.
19 *
20 * 功能说明:
21 * 在素数序列已经被构造的情况下, 判断n是否为素数效率很高；而在正整数中可以明确
22 * 确定的素数有:2、3、5、7、9...,假设已经有素数序列: p1, p2, ..., pn.现在要判断
23 * pn+1是否是素数, 则需要(1, sqrt(pn+1)]范围内的所有素数序列,而这个素数序列显然已
24 * 经作为p1, p2, .. pn的一个子集被包含了!有点递归的味道.
25 *
26 * MakePrimeArray的时间复杂度比较复杂, 而且它只有在初始化的时候才被调用一次.
27 * 在一定的应用范围内, 我们可以把近似认为makePrimes需要常数时间.
28 *
29 * 先构造素数数列,然后用整数与素数数列元素相除,若余数不为0则正整数为素数.
30 *
31 * 参考资料:http://linuxsir.org/bbs/thread278294.html
32 ***********************************************************************************/
33 #include <stdio.h>
34 #include <iostream>
35 #include <math.h>
36 usingnamespace std;
37
38 // PRIMENUMBER指定构造素数数组的元素个数
39 #define PRIMENUMBER 10
40
41 bool IsPrime(int PrimeArray[], constint nPositiveInteger);
42 void MakePrimeArray(int PrimeArray[], constint nPrimeNumber);
43
44 int main(int argc, char* argv[])
45 {
46 // 测试
47 int MyPrime[PRIMENUMBER] = {0};
48 int i = PRIMENUMBER;
49 MakePrimeArray(MyPrime, i);
50 for (int j=0; j<PRIMENUMBER; j++)
51 {
52 cout<<j<<"\t"<<MyPrime[j]<<endl;
53 }
54 if (IsPrime(MyPrime, 19))
55 cout<<"19 is prime"<<endl;
56 else
57 cout<<"19 is not prime"<<endl;
58 return0;
59 }
60
61 // 判断是否是素数
62 bool IsPrime(int PrimeArray[], constint nPositiveInteger)
63 {
64 if(nPositiveInteger <2)
65 returnfalse;
66 for(int i =0; PrimeArray[i]*PrimeArray[i] <= nPositiveInteger; ++i)
67 {
68 if(nPositiveInteger%PrimeArray[i] ==0)
69 returnfalse;
70 }
71 returntrue;
72 }
73
74 // 构造素数序列primes[]
75 void MakePrimeArray(int PrimeArray[], constint nPrimeNumber)
76 {
77 int i, cnt;
78 PrimeArray[0] =2;
79 PrimeArray[1] =3;
80 for(i =5, cnt =2; cnt < nPrimeNumber; i +=2)
81 {
82 bool flag =true;
83 flag = IsPrime(PrimeArray, i);
84 if(flag)
85 PrimeArray[cnt++] = i;
86 }
87 }
【参考资料 感谢作者】
[原创]浅析求素数算法: http://linuxsir.org/bbs/thread278294.html