エラトステネスの篩
エラトステネスの篩は素数判定法の代表的なアルゴリズムです。簡単に言えば、「1より大きい数の表から合成数を取り除き、残ったものを素数と判定する」ということです。
例えば、3000までの素数判定は次のようになります。
#include <stdio.h> #define MAX 3000 int main(void) { int i, j; int p[MAX]; //---初期化--- for(i=0 ; i<MAX ; i++) p[i] = 0; p[0] = 1; //---倍数を除外--- for(i=2 ; i<=MAX/2 ; i++){ for(j=2 ; i*j<=MAX ; j++){ if(p[i*j-1] == 0) p[i*j-1] = 1; } } for(i=0 ; i<MAX ; i++){ if(p[i] == 0) printf("%d\n", i+1); } return 0; }
| 固定リンク
「Algorithm」カテゴリの記事
- コラッツの問題(2008.02.21)
- フィボナッチ数を求める(2008.02.19)
- べき剰余を求める(2008.02.12)
- RSA暗号プログラム(2008.02.09)
- RSA暗号の公開鍵と秘密鍵を生成する(2008.02.08)
「C」カテゴリの記事
- CG法(2008.12.09)
- グラフの表示を遅延(2008.07.14)
- ポインタのこと、もっと知りたいんです。(2008.06.28)
- mallocで動的に確保してくれる関数(2008.05.27)
- Static(2008.04.17)
コメント
再帰使ってもいいかも。
投稿: クロ | 2008/02/02 18:43
私は再帰って苦手なので勉強になります。
クロさんてもしや・・・
投稿: Student | 2008/02/02 20:07
コマンドオプションで、計算対象となる最大数値を指定できるようにしてみました。
#include
#include
#include
#include
// definitions of constants, structures and variables
#ifndef BOOL
enum _BOOL {
FALSE = 0,
TRUE
};
#define BOOL enum _BOOL
#endif
// prototype definition
BOOL IsNumeric( char *pStr );
void main( int argc, char **argv, char **envp )
{
int i;
int iValue;
int iValueMax; // max value, which is also used as the size of an array
int *pValue;
int iMod; // surplus
BOOL bDivided;
// check the arguments
if( argc < 2 ) return;
if( !IsNumeric( argv[1] ) ) return;
// get max value
iValueMax = atoi( argv[1] );
// allocate an area on memory for the array of prime factors
pValue = (int *)malloc( sizeof(int) * (iValueMax + 1) );
if( pValue != NULL ){
memset( pValue, 0, (sizeof(int) * (iValueMax + 1)) );
// estimate prime factors, and add the array
for( iValue = 2; iValue <= iValueMax; iValue++ ){
bDivided = FALSE;
// skip even number
if( (iValue % 2) == 0 ) continue;
// judge if a number can be divided by any number,
// which has been already registered in the array
for( i = 2; i < iValue; i++ ){
if( *(pValue + i) ){
iMod = iValue % (*(pValue + i));
if( iMod == 0 ){
bDivided = TRUE;
break;
}
}
}
// add a prime factor to the array
if( !bDivided )
*(pValue + iValue) = iValue;
}
// output the prime factors on console
for( i = 2; i <= iValueMax; i++ ){
if( *(pValue + i) )
printf( "%d, ", *(pValue + i) );
}
// release the memory area
free( (void *)pValue );
}
}
BOOL IsNumeric( char *pStr )
{
int i;
// check the argument
if( pStr == NULL || (strlen(pStr) == 0) ) return FALSE;
// check if the specified string contains any non-numeric character
for( i = 0; i < (int)strlen(pStr); i++ ){
if( *(pStr + i) < '0' || *(pStr + i) > '9' ) return FALSE;
}
return TRUE;
}
投稿: | 2008/07/18 19:24
[一部訂正]
45行目:
if( (iValue % 2) == 0 ) continue;
↓
if( (iValue != 2) && ((iValue % 2) == 0) ) continue;
投稿: | 2008/07/18 19:28
[さらに訂正]
ヘッダ宣言は、HP上では<>は半角のままだとタグ扱いされてしまいますね。。。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <malloc.h>
投稿: | 2008/07/18 19:31