« 後悔と失意の週末 | Home | MathJaxを使ってみた »

April 12, 2012

素数日を調べるプログラムを書いてみた

長文こへだというブログの素数と素材とアホ夫婦の話という記事に、素数日だと思って2011年4月17日に婚姻届を出したのだが、20110417は、19の倍数(1058443 x 19)で素数ではなかったという話が載っていた。この夫婦の悲劇を繰り返してはならないという使命に燃え、素数日を調べるプログラムを書いてみた。ここでは素数日を、ある日付の西暦を4桁、月を2桁、日を2桁で表し、それをYYYYMMDDと並べた数値が素数である日付と定義する。

 それではまず、素数のリストを求めよう。素数は無数にあることが分かっている(数学ガール参照のこと)ので、求める範囲を2020年12月31日までとしよう。これは、私が結婚をすることを諦めるであろう期間の最大値であると根拠なく推定したからだ。ともあれ、C++で書くとこんな感じ。

#include<iostream>
#include<cstdio>

using namespace std;
const int MAX = 20201231;

int main(void)
{
	FILE *f;
	int n;

	if(NULL == (f = fopen("prime.dat", "wr")))
		return -1;

	fwrite("0", 1, 1, f); 
	for(int i=0; i<MAX; i++){
		fseek(f, i, SEEK_SET);
		fwrite("1", 1, 1, f); 
	}

	for(int i=2; i<=MAX/2; i++)
	{
		for(int j=2; MAX>(n=j*i); j++){
			fseek(f, n-1, SEEK_SET);
			fwrite("0", 1, 1, f);	
		} 
	}

	fseek(f, 0, SEEK_SET);
	for(int n=1; 0==feof(f);n++){
		if((int)'1' == fgetc(f))
			printf("%d\n", n);
	}

	return 0;
}

 C++とで書いたと言ってたくせにCじゃないかとか、最大値がマクロで指定されていてカッコ悪とか都合の悪いことは知らんぷりなのであしからず。素数の計算というと、べらぼうに時間がかかるイメージがあったのだが、実際に計算させてみるとCore2の2.4GHz、RAM2GByteで15分くらいだった。ちょっと拍子抜け。これならRubyで書いても問題なかったなぁと思った。 この出力をリダイレクトして、prime.lstというファイルに保存しておこう。

 このコードはシンプルなアイデアで、20201231個の「1」を書いたファイルを用意して、2の倍数、3の倍数、4の倍数...個目の1を0に変えていく。これをある大きさまで繰り返すと、素数個目の数が1で、それ以外が0になっている。つまり、1が何番目にあるか調べれば素数のリストを作ることができる。全く最適化していないので、無駄な計算をしている部分があるのだが、40行程度で書け、実行時間が実用上支障のない時間だったので、よしとする。

 次に、求めた素数が存在する日付であるか判定するプログラムが必要だ。PCが素数を探している間に、そのプログラムを書くことにしよう。こういうことはC/C++よりも、RubyやPerlがきっと得意なのでRubyで書くと、

#!/usr/bin/ruby

def calcEndofMonth(year, mon)
  t1 = Time.mktime(year, mon, 1);
  if(mon == 12)
    t2 = Time.mktime(year+1, 1, 1);
  else
    t2 = Time.mktime(year, mon+1, 1);
  end 

  return year*10000 + mon*100 + (t2-t1)/(3600*24);
end

def isCal(val)
  for year in 2012..2020
    for month in 1..12
      if((val > year*10000 + month*100) && (val <= calcEndofMonth(year, month)))
        return true;
      end
    end
  end
  return false;
end


f = File.open("prime.lst", "r");
f.each{|n|
  if(isCal(n.to_i))
    p n.to_i;
  end
}

これも簡単で、ある月に何日あるかを調べ、それをYYYYMMDDに並べて数を作る(たとえば、2012年4月であれば、4月には30日あるので20120430)。 次にその月の1日の数を作る(20120401)。そしてさきほど求めた素数がその範囲に入っているか調べる。入って入れば表示し、入っていなければ次の月で同じことを行う。これを求めたいすべての月で行うと、素数日を求めることができる。

 計算の結果、2012年1月1日から2020年12月31日までの間に182日あるようだ。計算した2020年までの素数日のリストもリンクしておく。

1 TrackBack

TrackBack URL: http://www.argv.org/~chome/blog/mt-tb.cgi/247

素数日を求める from ツムジのひとりごと on April 16, 2012 6:18 PM

*/--> *///--> 最近、自発的にコードを書くことがないなぁ…。 ということで今回も人様のブログのネタからです。何やら「素数日」を求めるらしい。 詳しい説明はこちらを見ていただくことにして…。   今回は「Date クラス」を使って実際の日付を出し、それを「yyyymmd Read More

About this Entry

This page contains a single entry by chomy published on April 12, 2012 8:34 PM.

後悔と失意の週末 was the previous entry in this blog.

MathJaxを使ってみた is the next entry in this blog.

Find recent content on the main index or look in the archives to find all content.