素数(素数)のいくつかの求め方

2609 ワード

素数は1とそれ自体でしか割り切れない数です.質量数を求めることはプログラム設計とアルゴリズムでよく見られるが,特に暗号学では質量数がよく用いられる.最も一般的な考え方は定義に基づいて質量数を求めることです
100以内の素数を求めると、次のアルゴリズムが書かれます.

int prime_1(int num)
{
	int cur=2;
	int count=0;   //      
	while (cur<num)
	{
		int factor=2;  //     2    
		while (factor<cur)
		{
			if (cur%factor==0)
			{
				break;
			}
			factor++;
		}
		if (factor==cur)
		{
			cout<<cur<<" ";
			count++;
		}
		cur++;
	}
	return count;
}

質量数ごとにそれより小さい数を除いて確定しなければならないので、無駄なことがたくさんあります.例えば11、例えば2から10まで9回判断してから確定します.では、判断回数を減らすことができるのでしょうか.n/2と判断すればいいだけで、後の数は判断しなくてもいいと考える人が多いのではないでしょうか.はい、n/2以内の数で除算できない限り、nは質量数です.もう1つの数nは別の数mで除去され,除去結果はkであることを考えてみよう.n=m*kと表すことができ、mとkをmの因子と呼ぶことができ、mとkの大きさには3つの場合があり、mk、私たちはm=k=sqrt(n)まで判断するだけで、後の判断は必要ありません.sqrt(n)より大きい因子があれば、もう1つの因子は必ずsqrt(n)より小さく、sqrt(n)より小さい場合はすでに判断したので、再度判断する必要はありません.これで判断回数を減らすことができます.

int prime_2(int num)
{
	int count=0;
	int cur=2;
	while (cur<num)
	{
		int maxcmp=(int)sqrt(cur);
		int factor=2;
		bool flag=true;  //     ，        false
		while(factor<=maxcmp)
		{
			if (cur%factor==0)
			{
				flag=false;
				break;
			}
			factor++;
		}
		if (flag)
		{
			cout<<cur<<" ";
			count++;
		}
		cur++;
	}
	return count;
}

1つの性質を利用する:1つの合数(非質量数)はいずれもそれより小さい質量数の積に分解することができる.12=2*2*3,15=3*5,もし我々が以前の素数を保存するならば、それより小さい素数で整除できるかどうかを判断するだけでよく、上の分析と結びつけてsqrt(n)より大きくない素数で整除できるかどうかを判断するだけでよく、この考え方に従って、以下のコードを書く.

int prime_3(int num)
{
	int count=0;
	int *result=new int[num];    //       
	result[0]=2;
	int cur=3;
	while(cur<num)
	{
		bool flag=true;  //     ，        false
		int maxcmp=(int)sqrt(cur);
		int index=0;
		while(result[index]<=maxcmp)
		{
			if (cur%result[index]==0) //               
			{
				flag=false;
				break;
			}
			index++;
		}
		if (flag)
		{
			count++;
			result[count]=cur;
		}
		cur++;
	}
	for (int index=0;index<count+1;index++)
	{
		cout<<result[index]<<" ";
	}
	delete []result;
	return count;
}

Java設計モードの[ウェルカムインタフェース]分析テンプレート方法(Template Method)モード

KMアルゴリズム学習ノート