第35页 第2章 神奇的素数

素数判断--孪生素数
中国剩余定理
RSA算法 实现：《典型密码算法C语言实现》TP312C /2533 
大整数运算
哥德巴赫猜想的程序验证
发现梅森素数
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
素数--大于1，只有1和本身两个因数的数。

Prime Number：http://zh.wikipedia.org/wiki/%E7%B4%A0%E6%95%B0

1.无规律性，被密码学大量使用；
2.齿轮啮合设计中，通过将齿数设计成素数增加两个齿轮中两个相同齿相遇啮合次数的3最小公倍数，增强齿轮耐用度，减少故障；
3.质数次数地使用杀虫剂是最合理的：都是使用在害虫繁殖的高潮期，而且害虫很难产生抗药性；
4.以质数形式无规律变化的导弹和鱼雷可以使敌人不易拦截；
5.多数生物的生命周期也是质数（单位为年），这样可以最大程度地减少碰见天敌的机会。

验证素数：确定性算法--试除法；随机算法(例如，AKS质数测试算法:多项式时间内检验)。
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
寻找1000以内的素数：
/*************************************************************************
	> File Name: prime_trydivision.c
	> Author: Nick
	> Mail: xjhznick@gmail.com 
	> Created Time: Tue 21 Apr 2015 09:25:31 AM CST
	> Description:试除法求解1000以内的素数(168个) , 100以内(25个)
 ************************************************************************/

#include<stdio.h>
#define NUMSIZE 100
int is_prime(int n);
int main(int argc, char *argv[])
{
	int i, count;
	for(count=0, i=2; i<NUMSIZE; i++){
		if(is_prime(i)){
			count++;
			printf("%-3d ", i);
			if(count%10 == 0) printf("\n");
		}
	}
	printf("\nTotal number of prime : %d\n", count);
	return 0;
}
int is_prime(int a)
{
	int i;

	if(a<=1) return 0; //<=1的数不是素数
/*
	int isPrime;

	isPrime = 1;
	for(i=2; i*i<=a; i++){
		if(a%i == 0){
			isPrime=0;
			break;
		}
	}
	return isPrime;
*/
	/*The lite edition of the above code block.*/
	for(i=2; i*i<=a; i++){
		if(a%i == 0){
			return 0;
		}
	}
	return 1;
}
/*************************************************************************
	> File Name: prime_eratosthenes.c
	> Author: Nick
	> Mail: xjhznick@gmail.com 
	> Created Time: Tue 21 Apr 2015 09:44:20 AM CST
	> Description: 使用Eratosthenes方法求素数
	筛选，筛去2,3,5,7的倍数..., 剩下的即为素数
 ************************************************************************/

#include<stdio.h>
#define NUMSIZE 1000
int main(int argc, char *argv[])
{
	int prime[NUMSIZE+1];
	int i, j, count;
	int bound;
	bound = NUMSIZE;
	/*Initialize:假定>=2的数都为prime，通过筛选找出非质数，置0
	 * prime      - 1
	 * none-prime - 0
	 */
	for(i=2; i<=bound; i++)
		prime[i] = 1;
	
	/*Core Algorithm*/
	for(i=2; i*i<=bound; i++){
		if(prime[i]){
			for(j=i*i; j<=bound; j++){
				if(prime[j] == 0) continue;
				if(j%i== 0) prime[j] = 0;
			}
		}
	}
	
	/*Count & Print*/
	count = 0;
	for(i=2; i<=bound; i++){
		if(prime[i]){
			count++;
			printf("%4d ", i);
			if(count%10 == 0) printf("\n");
		}
	}
	printf("\nTotoal number of prime is : %d\n", count);
	return 0;
}

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
强哥德巴赫猜想(欧拉)：任一大于2的偶数都可以写成两个素数之和。

算术基本定理证明每个大于1的正整数都可以写成素数的乘积，并且这种乘积的形式是唯一的。因此，素数也被称为自然数的“建筑的基石”。

素数定理描述素数的大致分布情况。