素数

　素数（そすう）というのは、「１より大きい整数で、１とその数以外で割り切れない数」のことです。例えば、「５」は１より大きい整数で、１と５でしか割り切れないので素数です。しかし、「６」は２や３でも割り切れるので、素数ではありません。
　とりあえず、1から100まで整数が素数かどうか調べてみると、以下のとおりです。

1	1より大きくない
2	素数
3	素数
4	2で割り切れる
5	素数
6	2,3で割り切れる
7	素数
8	2,4で割り切れる
9	3で割り切れる
10	2,5で割り切れる
11	素数
12	2,3,4,6で割り切れる
13	素数
14	2,7で割り切れる
15	3,5で割り切れる
16	2,4,8で割り切れる
17	素数
18	2,3,6,9で割り切れる
19	素数
20	2,4,5,10で割り切れる
21	3,7で割り切れる
22	2,11で割り切れる
23	素数
24	2,3,4,6,8,12で割り切れる
25	5で割り切れる
26	2,13で割り切れる
27	3,9で割り切れる
28	2,4,7,14で割り切れる
29	素数
30	2,3,5,6,10,15で割り切れる
31	素数
32	2,4,8,16で割り切れる
33	3,11で割り切れる
34	2,17で割り切れる
35	5,7で割り切れる
36	2,3,4,6,9,12,18で割り切れる
37	素数
38	2,19で割り切れる
39	3,13で割り切れる
40	2,4,5,8,10,20で割り切れる
41	素数
42	2,3,6,7,14,21で割り切れる
43	素数
44	2,4,11,22で割り切れる
45	3,5,9,15で割り切れる
46	2,23で割り切れる
47	素数
48	2,3,4,6,8,12,16,24で割り切れる
49	7で割り切れる
50	2,5,10,25で割り切れる

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

　このくらいまでなら、少しがんばれば素数かどうか調べることができますが、大きな数字になると素数かどうか調べるのは難しくなってきます。また、大きな素数と大きな素数をかけ合わせた数を見ても、いったい何と何をかけた数なのかを調べるのは非常に難しいため、数十桁から数百桁の大きな素数は暗号にも使われています。
　2008年8月現在、わかっている最も大きな素数は２を4311万2609回掛け合わせてから１を引いた数で、数百桁どころではなく、なんと1297万8189桁もあります。こちらのページにその数が書いてありますが、約16Mバイトもあるため、読み込むだけでも少し時間がかかります。 1行に57桁分ずつ書いてありますが、ページの一番下まで22万7688行もありますので、くれぐれも印刷しようなどとは思わないで下さい。