[Pythonアルゴリズム]#エラトスティンのふるい

5129 ワード
python algorithm テキストリンク
これは古代ギリシャの数学者エラトステネスが創造した少数の方法を探している.この方法はふるい出し数に似ており、「エラテストステロンのふるい」と呼ばれている.

解法


変数nを宣言し、numbers[ ]を(n+1)長さに設定し、Trueに初期化する.このとき、0と1は小数ではないので、Falseに変換されます.
エラトネスの実装部分では0と1が少数ではないため,2からforクエリ範囲を設定する.if文でnumbers[ i ]がtrueの場合、iは少数であることを示す.
非小数部を削除します.for文のiは小数であるため、i以外のiの倍数を変数jに宣言し、numbers[ j ]でFalseに変換して小数ではないことを示します.

コード#コード#

n = 100

numbers = [True] * (n+1)		# numbers의 길이를 n+1로 설정하고 0으로 초기화
numbers[0] = numbers[1] = False		# 0과 1은 소수가 아니므로 False로 변환
def prime_number():			# 에라토스테네스의 체 구현
  for i in range(2, int(n ** 0.5) + 1):	# 2부터 n의 제곱근까지 for문 반복
    if numbers[i] == True:		# numbers[i]가 True일 경우 i가 소수라는 의미
      for j in range(i+i, n+1, i):	# i를 제외한 i의 배수를 구하는 for문
        numbers[j] = False		# i의 배수는 소수가 아니므로 False로 변환
この場合、for i in range(2, n+1)ではなくint(n ** 0.5) + 1を行うことにより、n의 제곱근を範囲として速度を改善することができる.n**0.5の平方根求法では小数点が現れる可能性があるので、int関数で小数点以下の平方根を丸めて整数型にし、+1を範囲に設定します.
prime_number()				# 에라토스테네스의 체 실행
for i in range(n+1):			# numbers 모든 요소 반복하는 변수 i
  if numbers[i] == True:		# numbers[i]가 True라면 즉, i가 소수라면
    print(i)				# 소수인 i를 출력

アルゴリズム#アルゴリズム#



  • 2から素数を求めたい区間の全数をリストする.図中の灰色の矩形で囲まれた数はこれに相当する.

  • 2は小数で、右に2と書きます.(赤)
    自分以外の2の倍数を消す.

  • 残りの数は3が小数なので、右に3と書きます.(緑)
    自分以外の3の倍数を消す.

  • 残りの数のうち5は小数なので、右に5と書きます.(青)
    自分以外の5倍を消す.

  • 残りの数のうち7は小数なので、右に7と書きます.(黄色)
    自分以外の7の倍数を消す.
    • 上記の手順を繰り返すと、求めた区間のすべての小数点が残ります.
    1203アルゴリズム回答
    4.条件文