« ヒル暗号プログラム解説 | トップページ | Microsoft「Yahoo!を買収したいです」 »

2008/02/01

エラトステネスの篩

エラトステネスの篩は素数判定法の代表的なアルゴリズムです。簡単に言えば、「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;
}

|

« ヒル暗号プログラム解説 | トップページ | Microsoft「Yahoo!を買収したいです」 »

Algorithm」カテゴリの記事

C」カテゴリの記事

コメント

再帰使ってもいいかも。

#include <stdio.h>
#define N 3000
#define PN 500

int prime(int p[], int pn, int q)
{
int i, flag;
if (q > N) return pn;
for (i = 0;i < pn && p[i]*p[i]<= q; i++) {
flag = 1;
if (q%p[i] == 0) {
flag = 0;
break;
}
}
if (flag != 0) {
p[pn] = q;
pn++;
}
return prime(p, pn, q+2);
}

int main()
{
int i, pn;
int p[PN];
p[0] = 2;
p[1] = 3;
pn = prime(p, 2, 5);
for (i = 0;i < pn ; i++) {
printf("%d\n", p[i]);
}
printf("%d\n", pn);
return 0;
}

投稿: クロ | 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

コメントを書く



(ウェブ上には掲載しません)


コメントは記事投稿者が公開するまで表示されません。



トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/222903/17922838

この記事へのトラックバック一覧です: エラトステネスの篩:

« ヒル暗号プログラム解説 | トップページ | Microsoft「Yahoo!を買収したいです」 »