[アルゴリズム]2種類の質量数を求めるアルゴリズム(窮挙法,スクリーニング法),C言語で実現
2779 ワード
今日の试験のテーマは覚えられないので、テーマが公开されてからみんなに分析して、今日経典のアルゴリズムを言って、质数を求めて、多くの人がやはりその年の穷挙法を覚えていることを信じるようにしましょう、绝えず1つの数を1つの彼より小さい数の最大からsqrt(N)まで割って、それから结果を出して、アルゴリズムの时间の复雑度O(N^2)、最适化したアルゴリズムO(N*sqrt(N))、古典的なアルゴリズムは私は言わないで、初心者が分からないならば、伝言を残して、あるいは私に連絡することができます
コードは次のとおりです.
以下は現在多く使われている質量数を求める方法であり,もちろんより優れたアルゴリズムは「フェルマの小定理」を利用している.
素数の確率分布が線形に近いアルゴリズムの複雑さを実現することができるのは、今日は言わないで、興味がありますか?その続き
私に注目してください.最近時間があれば、コードを載せます.
さて、今日の主役:フィルタリング法は質量数を求めて、原理はすでに存在する配列のデータの中から必要な質量をフィルタリングすることです
数、1つのNの大きさの空間を必要として、Nは求めた質数の範囲で、経典のアルゴリズムに比べて比較的に浪費して、しかし効果的です
率が高く、O(N*LogN)で、広範囲の質量数を求めるのに適していますが、空間の浪費も客観的です.
原理:インデックスj=2,0,1から除外し、jのすべての倍数をふるい取り始め、j+1をふるい取り、
j=Nまでふるい分け、ふるい取り完了
具体的なアルゴリズムは以下の通りです.
--------------------------------------------------------------------------------------
-著作権宣言:
-本ページに特別な説明がなければ、本文の内容はすべて[李大仁ブログ]オリジナルで、本文の著作権は[李大仁ブログ]の所有に帰属します.
-転載を歓迎します.転載は必ず文章のページの明らかな位置に原文のリンクを提供し、出典を明記してください.本文の転載時にこの声明を保留することを歓迎します.
-文章タイトル:[アルゴリズム]2種類の質量数を求めるアルゴリズム(窮挙法、スクリーニング法)、C言語実現
-独立ブログ:李大仁ブログ
-永続リンク:http://www.lidaren.com/archives/244
--------------------------------------------------------------------------------------
以上の内容はブログ自動配信ツールにより自動配信され、最終的に表示内容や効果が原文内容とずれてしまうことがありますのでご了承ください.
コードは次のとおりです.
/* ，
*author CG
*2008 12 21
* O(N*sqrt(N))
*/
#include"stdio.h"
#include"math.h"
#define N 200/* */
int main() {
int i , j;
for(i = 2 ; i < N i br>
for(j = 2 ; j < intsqrti jjsqrtibr>
if(i % j == 0){
break;
}/*if*/
}/*for*/
if(j > (int)sqrt(i)){/* ？*/
printf("%-10d",i);/* */
}/*if*/
}/*for*/
return 0;
}/*main*/
以下は現在多く使われている質量数を求める方法であり,もちろんより優れたアルゴリズムは「フェルマの小定理」を利用している.
素数の確率分布が線形に近いアルゴリズムの複雑さを実現することができるのは、今日は言わないで、興味がありますか?その続き
私に注目してください.最近時間があれば、コードを載せます.
さて、今日の主役:フィルタリング法は質量数を求めて、原理はすでに存在する配列のデータの中から必要な質量をフィルタリングすることです
数、1つのNの大きさの空間を必要として、Nは求めた質数の範囲で、経典のアルゴリズムに比べて比較的に浪費して、しかし効果的です
率が高く、O(N*LogN)で、広範囲の質量数を求めるのに適していますが、空間の浪費も客観的です.
原理:インデックスj=2,0,1から除外し、jのすべての倍数をふるい取り始め、j+1をふるい取り、
j=Nまでふるい分け、ふるい取り完了
具体的なアルゴリズムは以下の通りです.
/*
*author CG
*2008 12 21
* O(N*LogN)
*/
#include "stdio.h"
#define N 200/* */
int main() {
double s , t;
int num[ N + 1 ] = {0};
int j = 2 ;/* ， 2 */
int i ;/* */
for(i=2 ; i
num[i] = i;/* , */
}
for(i = 2 ; i < N ibr>
j = 2;
while(j * i < N br>
num[j * i] = 0;
j++;
}/*while*/
}/*for*/
for(i = 2 ; i < N i br>
if(num[ i ] != 0)
printf("%-10d" , num[ i ]);
}/*for*/
return 0;
}/*main*/
--------------------------------------------------------------------------------------
-著作権宣言:
-本ページに特別な説明がなければ、本文の内容はすべて[李大仁ブログ]オリジナルで、本文の著作権は[李大仁ブログ]の所有に帰属します.
-転載を歓迎します.転載は必ず文章のページの明らかな位置に原文のリンクを提供し、出典を明記してください.本文の転載時にこの声明を保留することを歓迎します.
-文章タイトル:[アルゴリズム]2種類の質量数を求めるアルゴリズム(窮挙法、スクリーニング法)、C言語実現
-独立ブログ:李大仁ブログ
-永続リンク:http://www.lidaren.com/archives/244
--------------------------------------------------------------------------------------
以上の内容はブログ自動配信ツールにより自動配信され、最終的に表示内容や効果が原文内容とずれてしまうことがありますのでご了承ください.