エラトステネスの篩

エラトステネスの篩とは、素数を求めるアルゴリズムである。

概要

自然数を並べ、初めに1をマークし、次に2をマークして2の倍数を消去する。

次に残った数で一番小さい3をマークし3の倍数を消去する。

次に残った数で一番小さい5をマークし…

といった作業を繰り返すことで、素数を漏れなく求めることができる。以下は100までの表。赤色が素数である。

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60
61	62	63	64	65	66	67	68	69	70
71	72	73	74	75	76	77	78	79	80
81	82	83	84	85	86	87	88	89	90
91	92	93	94	95	96	97	98	99	100

エラトステネスの篩のいいところはnまで作業が終わればn²までの素数が漏れなく求まるというところである。この表で言えば10以下の素数を見つける手順が終わった時点で100までの素数すべてが明らかになる。

欠点はマークした素数以上の全ての数を毎回チェックして回る必要があるため時間がかかるところ。工夫しないとN以下の素数を調べるのにO(N√N)くらいの時間がかかるらしい。

関連動画

関連項目

• 自然数
• 素数
• 算数、数学
• 数学関連用語の一覧