第 $1$ 章 初 等 整 数 論
$\S\ 4.$ 素 数
$\boldsymbol{1.}$ 整除の関係においては整数の符号を考える必要がないから，本節では文字は正の整数を表わすことにする．整数はその約数の数からみれば，四つの種類に分かれる．まず $0$ は $0$ 以外のいかなる整数ででも割り切れるから，無限に多くの約数を有するものといわねばならない．
次に $1$ は $1$ 以外に約数を有しない．すなわちただ一つの約数を有する整数である．
$0$ と $1$ とは別格の整数である．
$a\gt1$ なる整数 $a$ は少なくとも $1$ と $a$ との二つの約数を有する．しかし或る数の約数というような語を制定したのは，$1$ やその数自身以外の約数を目標としたのであるから，$a$ の約数のうち，$1$ と $a$ とを除外して，その他の約数を真の約数ともいう．
さて $a\gt1$ である整数 $a$ が真の約数を有しないときには，$a$ を素数という．例えば $2$，$3$，$5$，$7$，$11$，$13$ などは素数である．
真の約数を有する整数を合成数という．それは，かような整数は素数の積として表わすことができるからである．例えば $4$，$6$，$8$，$9$，$10$ などは合成数である．
よって符号を考えずにいえば，整数は次の四種類に分かれる．
| $0$ | 無限に多くの約数を有する． |
| $1$（単数） | ただ一つの約数を有する． |
| 素数 | 真の約数を有しない． |
| 合成数 | 真の約数を有する． |
$\boldsymbol{2.}$ 次の定理は素数特有の性質を示すものである．
〔定理 $\boldsymbol{1.\ 8}$〕 二つ以上の整数の積が或る素数で割り切れるならば，因数のうち少なくとも一つがその素数で割り切れる．
〔証〕 $ab$ が素数 $p$ で割り切れるとする．
$\left(a,\ p\right)$ は $p$ の約数であるから，$1$ または $p$ に等しい．
$\left(a,\ p\right)=p$ ならば，$a$ は $p$ で割り切れる．
$\left(a,\ p\right)=1$ ならば，$b$ が $p$ で割り切れる（定理 $\ 1.\ 6$）．
よって $a$，$b$ のうち，少なくとも一つは $p$ で割り切れる．
すなわち二つの因数の積に関しては，定理は証明されたのである．$abc$ が素数 $p$ で割り切れるときは，$a$ または $bc$ が $p$ で割り切れる．したがって $a$ または $b$ または $c$ が $p$ で割り切れる．因数が三つより多くても同様である（数学的帰納法）．
〔注意〕 除数 $p$ が素数であるという仮定が必要である．例えば $3$ も $4$ も $6$ では割り切れないが $3\hspace{0.7mm}\cdotp4=12$ は $6$ で割り切れる．
上記の証明は定理 $\ 1.\ 6$に基づくことに注意するのが肝要である．
〔定理 $\boldsymbol{1.\ 9}$〕 合成数を素数の積に分解することができる．かつその分解の結果はただ一様である（補遺 $2$ 参照）．
〔証〕 最小の合成数 $4=2\times2$ に関しては定理は正しいから，数学的帰納法を用いる．すなわち $a$ を合成数として，$a$ よりも小さい合成数に関しては，定理は正しいと仮定する．
分解の可解性．$a$ は合成数であるから，$a=bc$，$1\lt b\lt a$，$1\lt c\lt a$ になるような $b$，$c$ がある．$b$ も $c$ も素数であるか，または仮定によって素数の積に分解されるから，$a$ も同様である．
分解の一意性．$a$ を素因数に分解して\[a=pp^\prime p^{\prime\prime}\cdots\cdots=qq^\prime q^{\prime\prime}\cdots\cdots\]を得たとすれば，$pp^\prime p^{\prime\prime}\cdots\cdots$ が素数 $q$ で割り切れるから，$p$，$p^\prime$，$p^{\prime\prime}$，$\cdots\cdots$ の中に $q$ で割り切れるものがある（定理 $1.\ 8$）．いま $p$ が $q$ で割り切れるとすれば，$p$ が素数であるから，$p=q$．故に\[p^\prime p^{\prime\prime}\cdots\cdots=q^\prime q^{\prime\prime}\cdots\cdots\]この相等しい数を $b$ とすれば，$b\lt a$ だから仮定によって二つの分解は合致する．
| $\ ^*\ $ | 巾は冪の略，ベキと読む． |
素因数への分解を用いるならば，整除に関する問題が簡明に解決される．
〔問題 $\boldsymbol{1}$〕 $a=p^\alpha q^\beta r^\gamma\cdots\cdots$ を素数巾への分解とすれば，$a$ のすべての約数は\[p^xq^yr^z\cdots\cdots\]において $0\leqq x\leqq\alpha$，$0\leqq y\leqq\beta$，$0\leqq z\leqq\gamma$，$\cdots\cdots$ とすることによって漏れなくまた重複なく得られる．
よって $a$ の約数の数（$1$ および $a$ を含めて）は\[T\left(a\right)=\left(1+\alpha\right)\left(1+\beta\right)\left(1+\gamma\right)\cdots\cdots\]である．
〔解〕 上記 $p^xq^yr^z\cdots\cdots$ が $a$ の約数であることは明らかである．それらの中に重複のないことは分解の一意性による．約数に漏れのないことも同様である．
〔問題 $\boldsymbol{2}$〕 $a$ のすべての約数の和を $S\left(a\right)$ とすれば\[S\left(a\right)=\frac{p^{\alpha+1}-1}{p-1}\hspace{0.7mm}\cdotp\frac{q^{\beta+1}-1}{q-1}\cdots\cdots\]（$p$，$q$，$\cdots\cdots$，$\alpha$，$\beta$，$\cdots\cdots$ は問題 $1$ と同様）．
〔解〕 問題 $1$ によって\[S\left(a\right)=\left(1+p+p^2+\cdots\cdots+p^\alpha\right)\left(1+q+q^2+\cdots\cdots+q^\beta\right)\cdots\cdots\] 〔問題 $\boldsymbol{3}$〕 $a$，$b$，$c$ が二つずつ互いに素なるときには\begin{alignat*}{2}T\left(abc\right)&=T\left(a\right)T\left(b\right)T\left(c\right)&&,\\[1mm]S\left(abc\right)&=S\left(a\right)S\left(b\right)S\left(c\right)&&.\end{alignat*} 因数の数はいくつでも同様．
〔問題 $\boldsymbol{4}$〕 $a$のすべての約数の積は $a^{\displaystyle\small\raise{0.5em}\frac{T\left(a\right)}{2}}$ に等しい．
〔解〕 $d$ を $a$ の約数とし，$a=dd^\prime$ と置く．$d$ をつぎつぎに $a$ のすべての約数にすれば $d^\prime$ も全体において $a$ のすべての約数になる．よって\[a^{T\left(a\right)}=\left(\textstyle\prod d\right){}^2,\]故に\[\textstyle\prod d=a^{\displaystyle\small\raise{0.5em}\frac{T\left(a\right)}{2}}.\] 〔注意〕 $a$ が平方数であるときには $T\left(a\right)$ は奇数であるが，その他の場合には偶数である．よって$a^{\displaystyle\small\raise{0.5em}\frac{T\left(a\right)}{2}}$が整数になるのである．
上記 $a=dd^\prime$ のような $a$ の約数 $d$，$d^\prime$ を互いに余約数という．
同様の立場から $S\left(n\right)\gt2n$ なる $n$ を豊数（abundant number），$S\left(n\right)\lt2n$ なる $n$ を輸数（deficient number）といっていた．
〔問題 $\boldsymbol{5}$〕 $a=2^{n-1}\left(2^n-1\right)$（ただし $n\gt1$ ）において $2^n-1$ が素数ならば，$a$ は完全数である．
逆に偶数の完全数はこのような数に限る（Euler）．
〔解〕 前段は明白である．その逆である後段を Euler が次のように証明した．この証明はすこぶる面白い．
$a$を偶数の完全数とし，$a=2^{n-1}b$，$n\gt1$，$\left(2,\ b\right)=1$ と置けば $S\left(a\right)=2a$ から（問題 $3$）\[\left(2^n-1\right)S\left(b\right)=2^nb,\]したがって\[S\left(b\right)=b+\frac{b}{2^n-1}\]を得る．故に $b/\left(2^n-1\right)$ は整数であるが，$n\gt1$ であるから，$b$ よりも小さい $b$ の約数である．すなわち $S\left(b\right)$ が $b$ の二つの相異なる約数の和に等しいから，$b$ はただ二つの約数を有する．故に $b$ は素数で $b/\left(2^n-1\right)=1$．すなわち $2^n-1$ は素数である．
〔注意〕 $2^n-1$ が素数であるには $n$ が素数であることが必要条件である（$2^{ab}-1$ は $2^a-1$ の倍数）．しかし，それは十分な条件ではない．
| $n$ | $2^n-1$ | $a$ | ||
| $\begin{alignat*}{1}2&\\3&\\5&\\7&\\11&\\13&\\17&\end{alignat*}$ | $\begin{alignat*}{1}3&\\7&\\31&\\127&\\2047&=23\times89\\8191&\\131071&\end{alignat*}$ | $\begin{alignat*}{1}6\\28&\\496&\\8128&\\――&\\33550336&\\8589869056&\end{alignat*}$ | ||
奇数の完全数は一つも知られていない．
特に $\left(a,\ b\right)=1$ ならば，$\left(a^m,\ b^n\right)=1$．
〔問題 $\boldsymbol{7}$〕 $\left(a_1,\ a_2,\ \cdots,\ a_m\right)\left(b_1,\ b_2,\ \cdots,\ b_n\right)=\left(a_1b_1,\ a_1b_2,\ \cdots,\ a_2b_1,\ a_2b_2,\ \cdots,\ a_mb_n\right)$．
〔問題 $\boldsymbol{8}$〕 $a_1$，$a_2$，$\cdots\cdots$，$a_n$ の中の少なくとも一つに含まれるすべての素因数を $p$，$q$，$\cdots\cdots$ とすれば
| $\hphantom{\left(\alpha_k\geqq0\right)}$ | \[a_k=\overset{p}{\textstyle\prod}\ p^{\alpha_k}\] | $\left(\alpha_k\geqq0\right)$ |
| $\operatorname{Min}$ | $\left(\alpha_1,\ \alpha_2,\ \cdots\cdots,\ \alpha_n\right)$ は $\alpha_1$，$\alpha_2$，$\cdots\cdots$，$\alpha_n$ の最小の値， |
| $\operatorname{Max}$ | $\left(\alpha_1,\ \alpha_2,\ \cdots\cdots,\ \alpha_n\right)$ は $\alpha_1$，$\alpha_2$，$\cdots\cdots$，$\alpha_n$ の最大の値 |
〔問題 $\boldsymbol{9}$〕 $a_1$，$a_2$，$\cdots\cdots$，$a_n$ の最大公約数を $d_1$，また $a_1a_2$，$a_1a_3$，$\cdots\cdots$，$a_{n-1}a_n$ の最大公約数を $d_2$ ，一般に $a_1$，$a_2$，$\cdots\cdots$，$a_n$ の中の $k$ ずつの積の最大公約数を $d_k$，最後に $a_1a_2\cdots\cdots a_n=d_n$ とすれば，おのおのの $d_k$ は $d_{k-1}$ で割り切れる．
もし $d_k/d_{k-1}=e_k$，（$e_1=d_1$）と置けば $e_k$ は $e_{k-1}$ で割り切れる．また\[e_1e_2\cdots\cdots e_n=a_1a_2\cdots\cdots a_n\]で，$e_n$ は $a_1$，$a_2$，$\cdots\cdots$，$a_n$ の最小公倍数に等しい．
〔解〕 問題 $8$ の応用．$\alpha_1$，$\alpha_2$，$\cdots\cdots$，$\alpha_n$ を大きさの順序に並べたものを ${\alpha_1}^\prime\leqq{\alpha^\prime}_2\leqq\cdots\cdots\leqq{\alpha^\prime}_n$ とすれば，$\displaystyle e_k=\overset{p}{\textstyle\prod}\ p^{\alpha^{\prime_k}}$ になる．
〔問題 $\boldsymbol{10}$〕 かりに $a$，$b$，$c$，$\cdots\cdots$ の最小公倍数を $\left\{a,\ b,\ c,\ \cdots\cdots\right\}$ で表わすことにする．しからば\[\left\{\left(a_1,\ m\right),\ \left(a_2,\ m\right),\ \cdots\cdots,\ \left(a_n,\ m\right)\right\}=\left(\left\{a_1,\ a_2,\ \cdots\cdots,\ a_n\right\},\ m\right).\]$($ $)$ は最大公約数を表わすのである．
〔解〕 $\displaystyle a_k=\overset{p}{\textstyle\prod}\ p^{\alpha_k}$，$\displaystyle m=\overset{p}{\textstyle\prod}\ p^\mu$ とすれば，問題は\[\operatorname{Max}\left[\operatorname{Min}\left(\alpha_1,\ \mu\right),\ \operatorname{Min}\left(\alpha_2,\ \mu\right),\ \cdots\cdots,\ \operatorname{Min}\left(\alpha_n,\ \mu\right)\right]=\operatorname{Min}\left[\operatorname{Max}\left(\alpha_1,\ \alpha_2,\ \cdots\cdots,\ \alpha_n\right),\ \mu\right]\]に帰する．まず $\mu\geqq\alpha_1$，$\alpha_2$，$\cdots\cdots$，$\alpha_n$ ならば，左辺は $\operatorname{Max}\left(\alpha_1,\ \alpha_2,\ \cdots\cdots,\ \alpha_n\right)$ ，右辺も同様である．その他の場合には，例えば $\alpha_1\gt\mu$ とすれば，左辺の括弧$[$ $]$のうちで，$\operatorname{Min}\left(\alpha_1,\ \mu\right)=\mu$ でかつ $\operatorname{Min}\left(\alpha_k,\ \mu\right)$ はもちろん $\mu$ より大でないから，左辺は $\mu$ に等しい．また $\operatorname{Max}\left(\alpha_1,\ \alpha_2,\ \cdots\cdots,\ \alpha_n\right)\geqq\alpha_1\gt\mu$ だから右辺も $\mu$ に等しい．
〔問題 $\boldsymbol{11}$〕 $l$ を $a$，$b$，$c$，$\cdots\cdots$ の最小公倍数とすれば，$l=a_0b_0c_0\cdots\cdots$，ただし，$a_0$，$b_0$，$c_0$，$\cdots\cdots$ はそれぞれ $a$，$b$，$c$，$\cdots\cdots$ の約数で，二つずつ互いに素である．
〔解〕 $l$ を合成する各素数巾は $a$，$b$，$c$，$\cdots\cdots$ のうち少なくとも一つに含まれている．$a$ に含まれるそれらの素数巾の積を $a_0$ とし，$b_0$，$c_0$，$\cdots\cdots$ も同様に定める．$a$，$b$，$c$，$\cdots\cdots$ の二つ以上に含まれているものは，随意にそれらに対応する $a_0$，$b_0$，$c_0$，$\cdots\cdots$ のうちの一つへ入れる．例えば，$a=2^5\hspace{0.7mm}\cdotp3\hspace{0.7mm}\cdotp7$，$b=2^2\hspace{0.7mm}\cdotp3^4\hspace{0.7mm}\cdotp7$ ならば，$a_0=2^5\hspace{0.7mm}\cdotp7$，$b_0=3^4$．または $a_0=2^5$，$b_0=3^4\hspace{0.7mm}\cdotp7$．
〔問題 $\boldsymbol{12}$〕 $p$ が素数ならば，二項係数 $\dbinom{p}{k}$（$p\gt k\gt0$）は $p$ で割り切れる． $\dbinom{p^n}{k}$（$p^n\gt k\gt0$）も $p$ で割り切れるが，$k$ がちょうど $p$ の $\kappa$ 乗で割り切れるならば，$p^{n-\kappa}$ で割り切れる．
〔解〕 $B=\dbinom{p^n}{k}$ とおけば，$B=\dfrac{p^n}{k}g$，ただし $g=\dbinom{p^n-1}{k-1}$．すなわち $kB=p^ng$．故に $kB$ が $p^n$ で割り切れる．したがって $B$ が $p^{n-k}$ で割り切れる．問題の初めの部分は $n=1$ なる場合である．
多項係数（補遺 $3$ 参照）\[\frac{p^n!}{a!b!c!\cdots\cdots}\hspace{5mm}\left(a+b+c+\cdots\cdots=p^n,\ a\geqq1,\ b\geqq1,\ c\geqq1,\ \cdots\cdots\right)\]に関しても同様である．$a$，$b$，$c$，$\cdots\cdots$ が $p$ で割り切れないならば，多項係数は $p^n$ で割り切れる（$a$，$b$，$c$，$\cdots\cdots$ の中にちょうど $p^k$ で割り切れるものがあれば，$p^{n-k}$ で割り切れる，$k\geqq0$）．
〔問題 $\boldsymbol{13}$〕 $n!$ に含まれる素因数 $p$ の最高巾の指数は\[\left[\frac{n}{p}\right]+\left[\frac{n}{p^2}\right]+\left[\frac{n}{p^3}\right]+\cdots\cdots=\overset{\infty}{\underset{k=1}{\textstyle\sum}}\left[\frac{n}{p^k}\right]\]である．$\left[\vphantom{\dfrac{n}{p}}\hphantom{\dfrac{n}{p}}\right]$ は Gauss の記号（$\S\ 1$，$3$ 頁）．
和は $n\geqq p^k$ なる $k$ の上にわたるのであるが，$n\gt p^k$ ならば $\left[\dfrac{n}{p^k}\right]$ は $0$ であるから，上記右辺のように書いておく．
〔解〕 $n!$ の因数なる $1$，$2$，$3$，$\cdots\cdots$，$n$ の中に $p$ の倍数が $n_1$，$p^2$ の倍数が $n_2$，$\cdots\cdots$ あるとすれば，求める指数は $n_1+n_2+\cdots\cdots$ である．しかるに $n_1=\left[\dfrac{n}{p}\right]$，$n_2=\left[\dfrac{n}{p^2}\right]$，$\cdots\cdots$
〔注意〕 $n$ を $p$ 進法で表わして\[n=a_0p^h+a_1p^{h-1}+\cdots\cdots+a_h\]とすれば，\begin{alignat*}{1}\left[\frac{n}{\hphantom{^{\ }}p\hphantom{^{\ }}}\right]=a_0p^{h-1}+a_1p^{h-2}+\cdots\cdots+a_{h-1},\\\left[\frac{n}{p^2}\right]=a_0p^{h-2}+a_1p^{h-3}+\cdots\cdots+a_{h-2},\\{\small\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots }\end{alignat*}よって問題の指数は\begin{alignat*}{1}a_0&\frac{p^h-1}{p-1}+a_1\frac{p^{h-1}-1}{p-1}+\cdots\cdots+a_{h-2}\frac{p^2-1}{p-1}+a_{h-1}\\&=\frac{\left(a_0p^h+a_1p^{h-1}+\cdots\cdots+a_h\right)-\left(a_0+a_1+\cdots+a_h\right)}{p-1}\\&=\frac{n-s}{p-1}\end{alignat*}ここで $s=a_0+a_1+\cdots\cdots+a_h$．それは $p$ 進法における $n$ のおのおのの位の「数字」の和である．
例えば $p=7$ として $n=120759$ を $7$ 進法で表わせば
すなわち $120759!$ はちょうど $7$ の $20125$ 乗で割り切れる． |
|
二項係数\[\binom{m}{n}=\frac{m\left(m-1\right)\cdots\cdots\left(m-n+1\right)}{n!}=\frac{m!}{n!\left(m-n\right)^{\ }\!!}\]が整数であることは，組合せの数としての意味から明白である．故に連続する $n$ 個の正の整数の積は $n!$ で割り切れる．これを直接に証明するために\[\binom{m}{n}=\frac{m!}{n!n^\prime!}\hspace{7mm}\left(n+n^\prime=m\right)\]とおいて，問題 $13$ を応用することができる．
任意の素因数 $p$ が分子 $m!$ と分母 $n!n^\prime!$ とに含まれる数を比較すれば\[\overset{\infty}{\underset{k=1}{\textstyle\sum}}\left[\frac{m}{p^k}\right]\geqq\overset{\infty}{\underset{k=1}{\textstyle\sum}}\left[\frac{n}{p^k}\right]+\overset{\infty}{\underset{k=1}{\textstyle\sum}}\left[\frac{n^\prime}{p^k}\right]\]$m=n+n^\prime$ から $\left[\dfrac{m}{p^k}\right]\geqq\left[\dfrac{n}{p^k}\right]+\left[\dfrac{n^\prime}{p^k}\right]$ を得るから，これは明白である．故に $m!$ は $n!n^\prime!$ で割り切れる．
〔問題 $\boldsymbol{14}$〕 既約分数 $m/n$ を部分分数に分解すること（$m\gt0$，$n\gt1$）．素数巾に分解して $n=p^\alpha q^\beta\cdots\cdots$ とすれば，\[\frac{m}{n}=\frac{x}{p^\alpha}+\frac{y}{q^\beta}+\cdots\cdots\pm s,\tag{$\ 1\ $}\] ただし $0\lt x\lt p^\alpha$，$0\lt y\lt q^\beta$，$\cdots\cdots$，$s\geqq0$ で，$x$，$y$，$\cdots\cdots$，$s$ はただ一組に限る．
〔解〕 まず $x$，$y$，$\cdots\cdots$ に関する附帯条件を考えに入れないならば（補遺 $4$ 参照），\[\frac{m}{n}=\frac{x}{p^\alpha}+\frac{y}{q^\beta}+\cdots\cdots\tag{$\ 2\ $}\]すなわち\[m=\frac{n}{p^\alpha}x+\frac{n}{q^\beta}y+\cdots\cdots\]は定理 $1.\ 7$ によって，整数解を有する．さて $\left(\ 2\ \right)$ においては $x$ は正でも負でも，$x/p^\alpha$ に適当な整数を加え，または引いてそれを正の真分数に化することができる．$y/q^\beta$，$\cdots\cdots$ に関しても同様であるから，$x$，$y$，$\cdots\cdots$ に関する附帯条件を入れても $\left(\ 1\ \right)$ の解はある．さてその一意性であるが，もしも同じ条件のもとにおいて\[\frac{m}{n}=\frac{x^\prime}{p^\alpha}+\frac{y^\prime}{q^\beta}+\cdots\cdots\pm s^\prime\]とすれば，引いて\[\frac{x-x^\prime}{p^\alpha}+\frac{y-y^\prime}{q^\beta}+\cdots\cdots\pm s\mp s^\prime=0.\]$n$ を掛けて分母をはらえば\[\left(x-x^\prime\right)q^\beta\cdots\]が $p^\alpha$ で割り切れることがわかる．よって $x-x^\prime$ は $p^\alpha$ で割り切れる（定理 $1.\ 6$）．しかるに $0\leqq x\lt p^\alpha$，$0\leqq x^\prime\lt p^\alpha$，$\left|x-x^\prime\right|\lt p^\alpha$．故に $x=x^\prime$．同様に $y=y^\prime$，$\cdots\cdots$ したがって $\pm s=\pm s^\prime$．
〔注意〕 $\left(\ 1\ \right)$ における部分分数 $x/p^\alpha$ をなお次のように分解することもできる．\[\frac{x}{p^\alpha}=\frac{a_1}{p}+\frac{a_2}{p^2}+\cdots\cdots+\frac{a_\alpha}{p^\alpha},\\[6mm]0\leqq a_1\lt p,\ 0\leqq a_2\lt p,\ \cdots\cdots,\ 0\lt a_\alpha\lt p.\]これは $x=a_1p^{\alpha-1}+a_2p^{\alpha-2}+\cdots\cdots+a_\alpha$（$p$ 進法）から得られる．
$\boldsymbol{3.}$ 素数が無限にあることは古代ギリシアで知られていた．次に掲げる証明は Euclid の幾何学原本に載っている．
〔定理 $\boldsymbol{1.\ 10}$〕 素数の数は無限である．
〔証〕 どのような大きな素数が与えられたとしても，それよりもなお大きい素数が必ず存在することを証明すればよい．
$p$ を与えられた素数として，$p$ 以下のすべての素数の積に $1$ を加えて\[a=2\hspace{0.7mm}\cdotp3\cdots\cdots p+1\]とする．
$a$ は素数であるか，または合成数であるかである．
$a$ が素数ならば，$a$ は $p$ よりも大きい素数である．
$a$ が合成数ならば，$a$ は或る素数 $q$ で割り切れる．しかるに $a$ は $2$ でも，$3$ でも，$\cdots\cdots$，$p$ でも割り切れないから，$q$ は $p$ よりも大きい素数である．
$\boldsymbol{4.}$ 素数を求める方法として，古代ギリシアの数学で知られていたいわゆる Eratosthenes のふるい（篩）というのがある．
自然数 $1$，$2$，$3$，$\cdots\cdots$ を大きさの順序に並べておいて，それをふるい分けて素数だけを残すのである．
まず $1$ は素数でないから除外する．その次の $2$ は素数である．$2$ から二つめずつの自然数にしるしを付けていけば，$2$ の倍数が標記される．それらはもちろん合成数であるからふるい落とされるべきものである．さて $2$ の次に残った $3$ は素数である．その $3$ から三つめずつの自然数にしるしを付けていけば，$3$ の倍数としてふるい落とされるべき数が標出される．そのとき $3$ の次に残った $5$ は自己よりも小さい素数 $2$，$3$ の倍数でないのであるから素数である．$5$ から五つめずつの自然数にしるしを付けるとき，$5$ の次に残っている $7$ はすなわち $5$ の次の素数である．このような操作を続行して $p$ なる素数に達したとすれば，$p^2$ よりも小さい自然数でしるしの付いていないものは，みな素数である．$p^2$ よりも小さい合成数は $p$ よりも小さい或る素数の倍数でなければならないから，すでにしるしが付けられていなければならない．
| $\underset{\raise{1em}-\vphantom{\equiv}}{1}\ $ | $\underset{\vphantom{\equiv}}{2}\ $ | $\underset{\vphantom{\equiv}}{3}\ $ | $\underset{\raise{1em}-\vphantom{\equiv}}{4}\ $ | $\underset{\vphantom{\equiv}}{5}\ $ | $\underset{=\vphantom{\equiv}}{6}\ $ | $\underset{\vphantom{\equiv}}{7}\ $ | $\underset{\raise{1em}-\vphantom{\equiv}}{8}\ $ | $\underset{\raise{1em}-\vphantom{\equiv}}{9}\ $ | $\underset{=\vphantom{\equiv}}{10}\ $ | $\underset{\vphantom{\equiv}}{11}\ $ | $\underset{=\vphantom{\equiv}}{12}\ $ | $\underset{\vphantom{\equiv}}{13}\ $ | $\underset{=\vphantom{\equiv}}{14}\ $ | $\underset{=\vphantom{\equiv}}{15}\ $ | $\underset{\raise{1em}-\vphantom{\equiv}}{16}\ $ | $\underset{\vphantom{\equiv}}{17}\ $ | $\underset{=\vphantom{\equiv}}{18}\ $ | $\underset{\vphantom{\equiv}}{19}\ $ | $\underset{=\vphantom{\equiv}}{20}$ |
| $\underset{=\vphantom{\equiv}}{21}\ $ | $\underset{\raise{1em}-\vphantom{\equiv}}{22}\ $ | $\underset{\vphantom{\equiv}}{23}\ $ | $\underset{=\vphantom{\equiv}}{24}\ $ | $\underset{\raise{1em}-\vphantom{\equiv}}{25}\ $ | $\underset{\raise{1em}-\vphantom{\equiv}}{26}\ $ | $\underset{\raise{1em}-\vphantom{\equiv}}{27}\ $ | $\underset{=\vphantom{\equiv}}{28}\ $ | $\underset{\vphantom{\equiv}}{29}\ $ | $\underset{\lower{0.1em}\equiv}{30}\ $ | $\underset{\vphantom{\equiv}}{31}\ $ | $\underset{\raise{1em}-\vphantom{\equiv}}{32}\ $ | $\underset{\raise{1em}-\vphantom{\equiv}}{33}\ $ | $\underset{\raise{1em}-\vphantom{\equiv}}{34}\ $ | $\underset{=\vphantom{\equiv}}{35}\ $ | $\underset{=\vphantom{\equiv}}{36}\ $ | $\underset{\vphantom{\equiv}}{37}\ $ | $\underset{\raise{1em}-\vphantom{\equiv}}{38}\ $ | $\underset{\raise{1em}-\vphantom{\equiv}}{39}\ $ | $\underset{=\vphantom{\equiv}}{40}$ |
| $\underset{\vphantom{\equiv}}{41}\ $ | $\underset{\lower{0.1em}\equiv}{42}\ $ | $\underset{\vphantom{\equiv}}{43}\ $ | $\underset{\raise{1em}-\vphantom{\equiv}}{44}\ $ | $\underset{=\vphantom{\equiv}}{45}\ $ | $\underset{\raise{1em}-\vphantom{\equiv}}{46}\ $ | $\underset{\vphantom{\equiv}}{47}\ $ | $\underset{=\vphantom{\equiv}}{48}\ $ | $\underset{\raise{1em}-\vphantom{\equiv}}{49}\ $ | $\underset{=\vphantom{\equiv}}{50}\ $ | $\underset{\raise{1em}-\vphantom{\equiv}}{51}\ $ | $\underset{\raise{1em}-\vphantom{\equiv}}{52}\ $ | $\underset{\vphantom{\equiv}}{53}\ $ | $\underset{=\vphantom{\equiv}}{54}\ $ | $\underset{\raise{1em}-\vphantom{\equiv}}{55}\ $ | $\underset{=\vphantom{\equiv}}{56}\ $ | $\underset{\raise{1em}-\vphantom{\equiv}}{57}\ $ | $\underset{\raise{1em}-\vphantom{\equiv}}{58}\ $ | $\underset{\vphantom{\equiv}}{59}\ $ | $\underset{\lower{0.1em}\equiv}{60}$ |
| $\underset{\vphantom{\equiv}}{61}\ $ | $\underset{\raise{1em}-\vphantom{\equiv}}{62}\ $ | $\underset{=\vphantom{\equiv}}{63}\ $ | $\underset{\raise{1em}-\vphantom{\equiv}}{64}\ $ | $\underset{\raise{1em}-\vphantom{\equiv}}{65}\ $ | $\underset{=\vphantom{\equiv}}{66}\ $ | $\underset{\vphantom{\equiv}}{67}\ $ | $\underset{\raise{1em}-\vphantom{\equiv}}{68}\ $ | $\underset{\raise{1em}-\vphantom{\equiv}}{69}\ $ | $\underset{\lower{0.1em}\equiv}{70}\ $ | $\underset{\vphantom{\equiv}}{71}\ $ | $\underset{=\vphantom{\equiv}}{72}\ $ | $\underset{\vphantom{\equiv}}{73}\ $ | $\underset{\raise{1em}-\vphantom{\equiv}}{74}\ $ | $\underset{=\vphantom{\equiv}}{75}\ $ | $\underset{\raise{1em}-\vphantom{\equiv}}{76}\ $ | $\underset{\raise{1em}-\vphantom{\equiv}}{77}\ $ | $\underset{=\vphantom{\equiv}}{78}\ $ | $\underset{\vphantom{\equiv}}{79}\ $ | $\underset{=\vphantom{\equiv}}{80}$ |
| $\underset{\raise{1em}-\vphantom{\equiv}}{81}\ $ | $\underset{\raise{1em}-\vphantom{\equiv}}{82}\ $ | $\underset{\vphantom{\equiv}}{83}\ $ | $\underset{\lower{0.1em}\equiv}{84}\ $ | $\underset{\raise{1em}-\vphantom{\equiv}}{85}\ $ | $\underset{\raise{1em}-\vphantom{\equiv}}{86}\ $ | $\underset{\raise{1em}-\vphantom{\equiv}}{87}\ $ | $\underset{\raise{1em}-\vphantom{\equiv}}{88}\ $ | $\underset{\vphantom{\equiv}}{89}\ $ | $\underset{\lower{0.1em}\equiv}{90}\ $ | $\underset{\raise{1em}-\vphantom{\equiv}}{91}\ $ | $\underset{\raise{1em}-\vphantom{\equiv}}{92}\ $ | $\underset{\raise{1em}-\vphantom{\equiv}}{93}\ $ | $\underset{\raise{1em}-\vphantom{\equiv}}{94}\ $ | $\underset{\raise{1em}-\vphantom{\equiv}}{95}\ $ | $\underset{=\vphantom{\equiv}}{96}\ $ | $\underset{\vphantom{\equiv}}{97}\ $ | $\underset{=\vphantom{\equiv}}{98}\ $ | $\underset{\raise{1em}-\vphantom{\equiv}}{99}\ $ | $\underset{=\vphantom{\equiv}}{100}$ |
| D. N. Lehmer | ：Factor table for the first ten millions ($1909$). |
| 〃 | ：List of prime numbers from $1$ to $10006721$ ($1914$). |