基本問題(9)

[ edit ]

*


概要

[ edit ]

*


ヒント

この課題で使うPythonの機能 (学習のヒント)

[ edit ]

この課題の解き方 (問題解決のヒント)

[ edit ]

  • この課題の解き方 (問題解決のヒント) ....
    • 春学期の前提科目でも例題に取り上げていたようですね.
*


実行例

[ edit ]

  • 実行例(1) ... クリックすると拡大します

fig-01

*


プログラム例: 本質的な部分 (授業中に順次公開します)

[ edit ]

  • 解答例の核心部分は,下記の 10 行の関数です.

# ==== 【関数定義】 エラトステネスの篩 ====================================================
def sieve_of_eratosthenes( n ):
    list_of_prime_numbers = [2]
    limit = int( n ** 0.5 )
    list_of_candidates = [i for i in range( 3, n+1, 2 )]
    while True:
        # print( list_of_candidates )
        prime_number = list_of_candidates.pop(0)
        list_of_prime_numbers.append( prime_number )
        if limit <= prime_number:
            return( list_of_prime_numbers + list_of_candidates )
        # 候補リストからpで割り切れないものだけドロップさせる(filtering out)
        list_of_candidates = filtering_out( list_of_candidates, prime_number )
  • ふるい落とす関数filtering_out()... 実質 6 行の関数

# ==== 【関数定義】 篩にかける ========================================================
#    ※ list_of_candidates から prime_number,およびその倍数を取り除いたリストを返す
def filtering_out( list_of_candidates, prime_number ):
    result = list()
    for x in list_of_candidates:
        if is_not_divisor( prime_number, x ):
            result.append( x )
    return( result )

[ edit ]

  • 【高度な話題/別解】: ふるい落とす関数filtering_out()... 実質 2 行の関数
    • 内包リスト表現を用いた方法です ⇒ 後日,取り上げる予定です

# ==== 【関数定義】 篩にかける ========================================================
#    ※ list_of_candidates から prime_number,およびその倍数を取り除いたリストを返す
def filtering_out( list_of_candidates, prime_number ):
    return( [ x for x in list_of_candidates if is_not_divisor( prime_number, x )] )
  • 【高度な話題/別解】: ふるい落とす関数filtering_out()... 実質 2 行の関数
    • 高階関数filter()を用いる方法 ⇒ 後日,取り上げる予定です

# ==== 【関数定義】 篩にかける ========================================================
#    ※ list_of_candidates から prime_number,およびその倍数を取り除いたリストを返す
def filtering_out( list_of_candidates, prime_number ):
    return( list( filter( lambda x: is_not_divisor( prime_number, x ), list_of_candidates ) ) )

[ edit ]

  • 【高度な話題/別解】: ふるい落とす関数filtering_out()
    • 以下のようには書けません.
      • なぜでしょう? ⇒ 後日(リスト処理の2周目くらい),取り上げる予定ですが...
        • シーケンスからループしつつ,要素を削除するのは注意が必要です

# ==== 【関数定義】 篩にかける ========================================================
#    ※ list_of_candidates から prime_number,およびその倍数を取り除く()
for x in list_of_candidates:
    if is_divisor( prime_number, x ):
        list_of_candidates.remove( x )
  • 【高度な話題/別解】: ふるい落とす関数filtering_out()
    • 以下なら大丈夫? ⇒ 後日(リスト処理の2周目くらい),取り上げる予定です
      • [:]はスライスですが,全体をコピーすることに相当します
        • コピーしたものでループすることで問題が生じません!!

# ==== 【関数定義】 篩にかける ========================================================
#    ※ list_of_candidates から prime_number,およびその倍数を取り除く()
#    ※ [:]はスライスですが,全体をコピーすることに相当します ⇒ コピーしたものでループする
for x in list_of_candidates[:]:
    if is_divisor( prime_number, x ):
        list_of_candidates.remove( x )

[ edit ]

  • 【異なる発想の別解(mark&sweep方式):リストの場合】: 本来の配列は,リストよりも添え字によるアクセスが非常に速いので,Python以外の配列をよく使う言語では,以下の解法の方が一般的です

    • mark&sweep方式...私は,このように名付けましたが,mark&sweepというのは元々,ガベージコレクタ実装方法の一つです.

      • 他にこのようには呼ぶ人は,まずいないと思いますので.注意してください (かえって混乱させてしまうかなぁ).

# ==== 【関数定義】 篩にかける ========================================================
#    ※ sieveリストに対し,prime_number,およびその倍数に,Falseマークを付ける
def mark_drop_numbers( sieve, prime_number, n ):
    for i in range( prime_number, n+1, prime_number ):
        sieve[i] = False

# ==== 【関数定義】 篩の中での先頭要素(最初にTrueが入っている要素の添え字)を見つける =====
#      ※前回見つけた素数から先をチェックすればよい
def top_of_sieve( sieve, prime_number ):
    top = prime_number
    while not sieve[top]:
        top += 1
    return( top )

# ==== 【関数定義】 篩を走査する(Trueが入っている要素の添え字を収集しリストで返す) =====
def sweep_sieve( sieve, n ):
    result = list()
    for i in range( 2, n+1 ):
        if sieve[i]:
            result.append( i )
    return( result )
  • 【異なる発想の別解(mark&sweep方式):辞書(dict)の場合】:

    • 辞書(dict)とは言っても順序が要りますね.
  • 【異なる発想の別解(mark&sweep方式):NumPyの配列の場合】:

*


プログラム例: 配布コード (授業中に順次公開します)

[ edit ]

  • 以下の解答例を配布します.
    • 本質部分は替えませんが,コメントやメインプログラム部分の実行例を,後々,分かり易く書き換える可能性はあります.

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# ==============================================================================
# * Copyright (c) 2018 IIJIMA, Tadashi
# *       (IIJIMA Laboratory, Dept. of Science and Technology, Keio University).
# ==============================================================================
# ソフトウェア工学[03] 基本課題[03]-(009a)  BP_03_009a_sieve_of_eratosthenes.py
# BP(Basic Problem) 03-009a: エラトステネスの篩によって素数のリストを求める
#   ※ 篩にかける ⇒ ドロップさせる要素を除いたリストを作る (forループを使う)
#        2018-10-17 飯島 正 (iijima@ae.keio.ac.jp)
# ==============================================================================
# ==== 【関数定義】 dはxの約数であるかどうか判定する関数(述語) =================================
def is_divisor( d, x ):
    return( x % d == 0 )
# -----------------------------------------------------------------------------
def is_not_divisor( d, x ):
    return( x % d != 0 )
# ==============================================================================
# ==== 【関数定義】 篩にかける ========================================================
#    ※ list_of_candidates から prime_number,およびその倍数を取り除いたリストを返す
def filtering_out( list_of_candidates, prime_number ):
    result = list()
    for x in list_of_candidates:
        if is_not_divisor( prime_number, x ):
            result.append( x )
    return( result )
# ==============================================================================
# ==== 【関数定義】 エラトステネスの篩 ====================================================
def sieve_of_eratosthenes( n ):
    list_of_prime_numbers = [2]
    limit = int( n ** 0.5 )
    list_of_candidates = [i for i in range( 3, n+1, 2 )]
    while True:
        # print( list_of_candidates )
        prime_number = list_of_candidates.pop(0)
        list_of_prime_numbers.append( prime_number )
        if limit <= prime_number:
            return( list_of_prime_numbers + list_of_candidates )
        # 候補リストからpで割り切れないものだけドロップさせる(filtering out)
        list_of_candidates = filtering_out( list_of_candidates, prime_number )
# ==============================================================================
# ===== 【メイン・プログラム】 =====
# ----- オープニングメッセージ -----
print( "指定された正整数までの素数のリストを求める: " )
print( "    ※エラトステネスの篩を用いる" )
print()

# ----- パラメータの入力 -----
x = int( input( "正の整数を入力してください>>> " ) );
print()

# ----- 計算と結果の表示 -----
result = sieve_of_eratosthenes( x )
print( result )
# ==============================================================================
*
*

SoftEng: Python/Prog/Practice/Basic/03/BP_009a (last edited 2018-10-21 12:55:26 by TadashiIijima)