リストを使って効率よく素数を求める
Python で素数を出力するプログラムを何パターンか書いただけ．
与えられた数までの素数を出力
標準入力である数を与えられたとき，その数までの素数を出力します．
ソースコード
n = int(input())
for i in range(2, n):
for j in range(2, i+1):
if i % j == 0:
if i == j:
print(i)
else:
break
i は割られる数で，範囲は [2, n)
j は割る数で，範囲は [2, i+1)
素数の条件は，約数に 1 とその数自体以外を持たないことです．1 は割る数に含まないようになっているので，初めて j で割り切れたときに j = i であれば良いわけです．
実行しながら求めた素数をリストにし，それを割る数にすることで，もっと効率よくプログラムを実行することができます．
逐一出力するのではなく，最後にまとめて出力する場合は次のようになります．
n = int(input())
primeN = []
for i in range(2, n):
for j in range(2, i+1):
if i % j == 0:
if i == j:
primeN.append(i)
else:
break
for i in primeN:
print(i)
与えられた数までの素数の個数を出力
先ほどのプログラムを少し変えるだけで素数の個数を求めることができます．
ソースコード
n = int(input())
count = 0
for i in range(2, n):
for j in range(2, i+1):
if i % j == 0:
if i == j:
count += 1
else:
break
print(count)
求めた素数をすぐに出力していたものを count で数えるだけです．
ちなみに，Python にはインクリメント演算子がありません...！
効率の向上
上記の方法では与えられた上限となる数 n に対して割る数を 2 から順に n まで増やし，n 以外で割れないことを利用して素数を求めていましたが，数字が大きくなれば実行時間が長くなります．
そこで，素数のリストを使って効率よく素数を求めてみます．(アドバイスありがとうございました！)
素数リスト
素数をリストにすると，今まで求めた素数で割れるか割れないか調べるだけで，次の素数を求めることができます．
文字で書くと少しわかりにくいので，例を挙げてみましょう．
素数のリスト 2, 3, 5 があるとします．
6 を素数のリストに含まれる数字で割ろうとすると，2 もしくは 3 で割り切れるので，6 は素数ではありません．次に，1 増やして 7 を素数のリストに含まれる数字で割ってみます．どの数字でも割ることができないので，7 は素数であることが分かります．
この考え方を利用してコードを書いていきます．
リストの使い方
Python には配列がなく，似たような機能としてリストがあります．
Java などでは配列の個数は固定ですが，Python のリストは長さが可変なので，慣れると使いやすい気もします．
リストの書き方と，リストへ要素を追加する方法は以下になります．
list = [2, 3] # リストの書き方(数値)
list.append(5) # リストの要素の追加
リストにはいくつか機能がありますが，今回利用するのは append() メソッドです．
これを実行すると，list の中身は 2, 3, 5 となります．
ソースコード
最初に 2 だけ素数リストの要素に用意しておくと，後は自動的に素数をリストに追加していきます．
n = int(input())
primeN = [2]
for i in range(2, n):
for j in range(len(primeN)):
if i % primeN[j] == 0:
break
else:
if j == len(primeN) - 1:
primeN.append(i)
for i in primeN:
print(i)
どのくらい効率が上がったかというと，n = 10000 としたとき，前回の方式では約 0.78841 秒かかったのに対し，今回の方式では約 0.27276 秒で素数の数を求めることができています．
やはり素数リストを使ったほうが計算が早く終わるようです．
追記 2016/09/19
もし n = 1 を入力したとしても，上のコードだと 2 を素数として出力してしまうので修正しました．
n = int(input())
primeN = []
tmp = 2
for i in range(2, n):
if primeN:
for j in range(len(primeN)):
if i % primeN[j] == 0:
break
else:
if j == len(primeN) - 1:
primeN.append(i)
else:
if n > tmp:
primeN.append(i)
for i in primeN:
print(i)
追記 2019/02/01
昔こんな記事書いてたんだなぁと振り返ったら，すごく初心者感ありますね．今もひよこですが．
追記のコードを n=10000 で試したら約 0.155196586 秒でした．
n = int(input('number: '))
if n >= 2:
prime_nums = [2]
for i in range(3, n + 1):
for p in prime_nums:
if i % p == 0:
break
else:
prime_nums.append(i)
リストをわざわざ range() で呼ばず，かつ for else 文を使うと約 0.052504463 秒まで縮みました．リスト内包表記使ったらもっと早くできるかもしれないですね．