特殊なライブラリを使わずに短くシンプルに書けるとなんだかハッピ～～～、それが素数数え上げアルゴリズム。この記事ではその基本的な骨組みについて個人的に考えたことをざっくりと説明します。
（まず）素数とは
1と自分以外に約数を持たない数のことです。
素数の数え方2種
数え方① ひとつひとつの数に対して約数の有無を調べる
まずは、定義通りの方法。素数のリストを作り、素数判定の対象となる数ひとつひとつに対して素数リスト内の数の倍数でないか調べていく。
処理の流れ：
①素数のリストを作る。最初は2だけ入れておく。（1は素数ではない。）pythonの場合primes=[2]など
②判定対象の数（まだ素数かどうかわかっていない自然数）を入れる変数を用意する。最初の数は3にする。n=3など
③すでに素数リストに入っている素数で判定対象の数を割りきれないか、ループなどを使って調べる。素数リストに入っているどの数でも割り切れなかったらその数は素数なので、素数リストに追加する。
④判定対象の数に+1をする。
⑤ ③→④を繰り返す。（判定対象の数の上限に達するまで or 素数の数が一定数に達するまで）
（判定対象の数→素数のリスト→素数判定（YesかNoか））の変化：
(3→[2]→Yes)
(4→[2,3]→No)
(5→[2,3]→Yes)
(6→[2,3,5]→No)...
数え方② 判定対象の数のリストから素数の倍数を消していく
判定対象の数をすべて羅列したリストを作り、すでに素数だとわかっている数の倍数を判定対象の数のリストから消していく。（例えば2は素数なので、2,4,6,8,10...は真っ先にリストから消される。）消された後に残った数のうち一番小さい数は必然的に素数になる。
処理の流れ：
①判定対象の数のリストを作る。pythonならnumbers=[3,4,.....100]など
②素数を記録するリストも作っておく。primes=[]など
③判定に使う素数を入れる変数を用意する。prime=2(numbers[0]もアリ)
⑥素数のリストに③を記録しておく。
④判定対象の数のリストからさきほどの素数の倍数を消す。numbersの例だと[3,5,7,9....99]となる。
⑤残った数のうち一番小さい数(初回は3)を判定に使う素数に設定する。
⑦ ④→⑥を繰り返す。（素数の数が一定数に達するまで）
（判定対象の数のリスト→判定に使う素数→判定後の判定対象のリスト）の変化
([3,4,5,6,7,...,100]→2→[3,5,7,,9,...,97,99])
([3,5,7,,9,...,97,99]→3→[5,7,11,13,17,...,95,97])
([5,7,11,13,17,...,95,97]→5→[7,11,13,...,89,97])...
①と②のコード例（python）
①(ひとつひとつの数に対して約数の有無を調べる)のコード例
limit=30
primes=[2]
n=3
while n<=limit:
for prime in primes:
isPrime=True
if n%prime==0:
isPrime=False
break
if isPrime==True:
primes.append(n)
n+=1
print(primes)'
②（判定対象の数のリストから素数の倍数を消していく）のやり方
numbers=[x for x in range(2,31)]
primes=[]
while len(numbers)>=1:
prime=numbers[0]
primes.append(prime)
for n in numbers:
if n%prime==0:
numbers.remove(n)
print(primes)
最後に
①のやり方だと素数リストが長くなるたびに繰り返し回数が増えていくので、大きな数の時は②の方がよさそうですね！