根号法、埃氏法、欧拉筛选。三种方法求素数_求质数开根号+2

先上开根号求素数

一个数N的最小质因子，必定小于开根号N：
数学表达：a*b=N,若a<开根号N，b必定>开根号N，所以只要求2~开根号N，即可判断N是不是素数。


反证法
如果数N的最小质因子a大于开根号N，那数N的另一个因子b，（b和a构成一对N的约数），
必定大于a，那么也大于根号N，
这时候，a*b必定大于N，所以原命题正确




自己的证明：一个数N，那么有 0~开跟号N=>左域  ，开根号N~N-1=>右域。   
  开根号N就在中间了，开根号N*开根号N=N，这个是最平衡的组合了。
  假设N=a*b。a和b！=开根号N，那么 a和b必定一个在左域，一个在右域。
  如果a和b都取值于左域，那么a*b必定<N  
  如果a和b都取值于右域，那么a*b必定>N
  所以原命题成立。

代码过于简单，这里就不贴出来了，只讲述原理。

埃氏法求素数

Eratosthenes筛选法求解质数
思路：用一句形象的话来形容这个算法，就是一山难容二虎。例如，2是一个质数，那么他可以留在质数表里面，
      那么，如果2后面的数能够被2整除的，肯定就不是素数，所以剔除之。（只要前面的有一个质数【第1虎】，后面为他的倍数的数就肯定不是素数【第2虎】根据素数的定义）

/* Note:Your choice is C IDE */
#include "stdio.h"
/*
//优化前的埃氏算法主要有1个缺点
//1.求素数倍数的时候，是一个一个得求，（比如求2的倍数的时候，是直接从2开始，然后一个一个往上加，一直求到n），所以它所检测过数是一个连续的序列
//
void main()
{
    int n,i;
    int m[101];
    for(n=1;n<=100;n++)
    {
    	m[n]=n;	
    }
    
    for(n=2;n<=100;n++)
    {
    	if(m[n]!=0)
    	{
    		for(i=n+1;i<=100;i++)
    		{
    			if(m[i]%n==0)
    			{
    				m[i]=0;	
    			}	
    		}	
    	}
    }
    
    for(n=1;n<=100;n++)
    {
    	if(m[n]!=0)
    	{
    		printf("%d\n",m[n]);
    	}
    }
    
}*/
 
 
//优化后的埃氏算法，主要优化2点
//1.求6的倍数，不从2开始乘，（既2*6，因为前面算2的时候，已经算过了），直接从6*6开始
//2.对求过的数进行判断，如果已经不是素数了，就直接跳过
 
 
//对比优化之前的埃氏算法，检测素数倍数的时候，是以点的方法去算，优化之前是以一个连续的序列去算的（比如求2的倍数，优化之前是从2一直加到N-1。优化后的是直接用  2*2 2*3 2*4 ····2*n 《N，）优化后的埃氏算法，求素数的所检测过的数是一个一个点，那效果肯定比之前的一大串序列好
void main()
{
	int m[101];
	int i,j;
	for(i=1;i<=100;i++)
	{
		m[i]=i;	
	}	
	
	for(i=2;i<=100;i++)
	{
		for(j=i*i;j<=100;j=j+i)
		{
			if(m[j]!=0)
			{
				if(m[j]%i==0)
				{
					m[j]=0;	
				}
			}	
		}
	}
	
	
	for(i=1;i<=100;i++)
	{
		
			if(m[i]!=0)
			{
				printf("%d\n",m[i]);
			}	
	}
	
}

先介绍一下欧拉筛选的原理：  
假设prime数组现在存放着i之前的素数。
i=6 ，prime【0】=2，prime【1】=3，prime【2】=5；
如果，i%prime【0】=0，那么（i*prime【1】）%prime【0】必定也会定于0；
换成具体数字，6%2=0；（6*3）%2=0
因为，i能整除prime【0】，说明prime【0】是i的因子。那不管i乘以多少，结果必定能够整除prime【0】；


也就是说，当未来i跳到9的时候，2*9，会再次进行一次筛选，那么就存在冗余了。







下面介绍整个算法的流程
for（i=>2~n）
{
if（i是素数）
加入到prime数组中，prime下标top=top+1
for(j=>【遍历prime数组，下边从0开始】&&prime[j]*i<=n)
先把i*prime[j]标记为素数（根据素数的定义，某个数的倍数绝对不是素数）
if(i能整除prime[j])
跳出循环


}


也就是说，不管i是不是素数。先把i*prime【0】筛选出来。
如果这个数是素数，那么就直接把i之前的素数跟他相乘，得出来的数标记为素数。


如果这个数是合数，那么就根据上面介绍的原理对i进行处理。
如果i不是素数，那么他必定能整除prime【0-top】（既当前的已经筛选出来的素数，也就是i之前的素数。）中的某一个素数。

/* Note:Your choice is C IDE */
#include "stdio.h"
int p[10000];
int prime[10000];
int n=100;
void main()
{
	int i ,j,top=0;
    for(i=2;i<=n;i++)
    {
    	if(p[i]==0)
    	{
    		prime[top++]=i;		
    	}	
    	
    	for(j=0;j<top&&i*prime[j]<=n;j++)
    	{
    		p[i*prime[j]]=1;
    		if(i%prime[j]==0)
    		{
    			break;	
    		}	
    	}
    }
    
    for(i=0;i<top;i++)
    {
    	printf("%d\n",prime[i]);	
    }
}