Diff for "Python/Prog/Practice/Basic/02/BP_008a"

Differences between revisions 1 and 6 (spanning 5 versions)

基本課題[02]

基本(1a)

基本(2a)

基本(3a)

基本(4a)

基本(5a)

基本(6a)

基本(7a)

基本(8a)

基本問題(8)

演習(8)

基本課題(8a)

【関数定義】

試し割り法による素数判定

BP_02_008a_judge_prime_number_by_trial_division.py
解答は基本的に，下記 6 行です．
- 2～√xまでの整数で順に割ってみて，割り切れたら，(1と)自分自身以外に約数があることを意味する．
  - 逆に言えば，割り切れる整数が，その範囲内に存在しなければ，素数であることを意味する
- x**0.5は，平方根です．したがって，mathモジュールのsqrt()関数を使ってもかまいません
- 与えられた整数以下の素数を列挙するのであれば，エラトステネスの篩(ふるい)を使うのがよいでしょう
  - 後日，リストを取り上げてからやりましょう

   1 def is_prime_number( x ):
   2     last = int( x ** 0.5 )
   3     for i in range( 2, last + 1 ):
   4         if is_divisor( i, x ):
   5             return( False )
   6     return( True )

ここで，is_divisor()関数は，単に，約数かどうか判定する以下の2 行の関数ですが，関数にするまでもないですね．

   1 def is_divisor( d, x ):
   2     return( x % d == 0 )

なので，もうすこし短く書けそうです．

   1 def is_prime_number( x ):
   2     for i in range( 2, int( x ** 0.5 + 1 ) ):
   3         if x % d == 0 :
   4             return( False )
   5     return( True )

   1 #!/usr/bin/env python
   2 # -*- coding: utf-8 -*-
   3 # ==============================================================================
   4 # * Copyright (c) 2018 IIJIMA, Tadashi
   5 # *       (IIJIMA Laboratory, Dept. of Science and Technology, Keio University).
   6 # ==============================================================================
   7 # ソフトウェア工学[02] 基本課題[02]-(008a)  BP_02_008a_judge_prime_number_by_trial_division.py
   8 # BP(Basic Problem) 02-008a: 試し割による素数判定
   9 #        2018-10-03 飯島 正 (iijima@ae.keio.ac.jp)
  10 # ==============================================================================
  11 # dはxの約数である
  12 def is_divisor( d, x ):
  13     return( x % d == 0 )
  14 # ==============================================================================
  15 # 2 ～　√xの間に，約数が存在しないなら，xは素数
  16 def is_prime_number( x ):
  17     last = int( x ** 0.5 )
  18     for i in range( 2, last + 1 ):
  19         if is_divisor( i, x ):
  20             return( False )
  21     return( True )
  22 # ==============================================================================
  23 # ===== 【メイン・プログラム】　 =====
  24 # ----- オープニングメッセージ -----
  25 print( "試し割り法によって，素数か否かを判定する関数： " )
  26 print( "　　50以下の素数列を表示するために使ってみる．　" )
  27 print( "  指定の数以下の素数を列挙するには，「エラトステネスの篩」を使う方が効率がよいが，" )
  28 print( "  その実装は，リストを取り上げてから，後日，行う" )
  29 
  30 # ----- 計算と実行結果の表示 -----
  31 for i in range( 2, 50 ):
  32     if is_prime_number( i ):
  33         print( i, end=", " )
  34 print()
  35 # ==============================================================================

SoftEng: Python/Prog/Practice/Basic/02/BP_008a (last edited 2018-10-28 14:44:43 by TadashiIijima)

-  ⇤ ← Revision 1 as of 2018-10-09 06:15:59 → 
  Size: 746
  Editor: TadashiIijima
  Comment:
+   ← Revision 6 as of 2018-10-10 15:11:45 → ⇥
  Size: 3857
  Editor: TadashiIijima
  Comment:
-Deletions are marked like this.
+Additions are marked like this.
 Line 10:
-==== 基本問題() ====
+==== 基本問題(8) ====
 Line 12:
- ||演習()     ||<-2>                                       ||
 ||演習(a)    ||[[../BP_00a||target="_blank"]]||    ||
+ ||<|2>演習(8)     ||<|2>基本課題(8a)||<|2>【関数定義】||<|1>[[https://ja.wikipedia.org/wiki/試し割り法|試し割り法]]による素数判定||
 ||<|1>                                [[../BP_008a|BP_02_008a_judge_prime_number_by_trial_division.py|target="_blank"]]||
 Line 15:
- * 解答は基本的に，下記  行です．
  * 問題の回答としては，これだけで十分です．
  * 自分自身のソフトウェア開発のためには，できるだけコメントをつける習慣をもってください．
+ * 解答は基本的に，下記 6 行です．
  * 2～√xまでの整数で順に割ってみて，割り切れたら，(1と)自分自身以外に約数があることを意味する．
   * 逆に言えば，割り切れる整数が，その範囲内に存在しなければ，素数であることを意味する
  * x**0.5は，平方根です．したがって，mathモジュールのsqrt()関数を使ってもかまいません
  * 与えられた整数以下の素数を列挙するのであれば，[[https://ja.wikipedia.org/wiki/エラトステネスの篩|エラトステネスの篩(ふるい)]]を使うのがよいでしょう
   * 後日，リストを取り上げてからやりましょう
-Line 20:
+Line 23:
+def is_prime_number( x ):
    last = int( x ** 0.5 )
    for i in range( 2, last + 1 ):
        if is_divisor( i, x ):
            return( False )
    return( True )
-Line 23:
+Line 31:
- *
+ * ここで，is_divisor()関数は，単に，約数かどうか判定する以下の2 行の関数ですが，関数にするまでもないですね．
-Line 26:
+Line 34:
+def is_divisor( d, x ):
    return( x % d == 0 )
}}}
-Line 27:
+Line 38:
+ * なので，もうすこし短く書けそうです．

{{{#!highlight python
def is_prime_number( x ):
    for i in range( 2, int( x ** 0.5 + 1 ) ):
        if x % d == 0 :
            return( False )
    return( True )
}}}

{{{#!highlight python
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# ==============================================================================
# * Copyright (c) 2018 IIJIMA, Tadashi
# *       (IIJIMA Laboratory, Dept. of Science and Technology, Keio University).
# ==============================================================================
# ソフトウェア工学[02] 基本課題[02]-(008a)  BP_02_008a_judge_prime_number_by_trial_division.py
# BP(Basic Problem) 02-008a: 試し割による素数判定
#        2018-10-03 飯島 正 (iijima@ae.keio.ac.jp)
# ==============================================================================
# dはxの約数である
def is_divisor( d, x ):
    return( x % d == 0 )
# ==============================================================================
# 2 ～　√xの間に，約数が存在しないなら，xは素数
def is_prime_number( x ):
    last = int( x ** 0.5 )
    for i in range( 2, last + 1 ):
        if is_divisor( i, x ):
            return( False )
    return( True )
# ==============================================================================
# ===== 【メイン・プログラム】　 =====
# ----- オープニングメッセージ -----
print( "試し割り法によって，素数か否かを判定する関数： " )
print( "　　50以下の素数列を表示するために使ってみる．　" )
print( "  指定の数以下の素数を列挙するには，「エラトステネスの篩」を使う方が効率がよいが，" )
print( "  その実装は，リストを取り上げてから，後日，行う" )

# ----- 計算と実行結果の表示 -----
for i in range( 2, 50 ):
    if is_prime_number( i ):
        print( i, end=", " )
print()
# ==============================================================================

演習(8)	基本課題(8a)	【関数定義】	試し割り法による素数判定
			BP_02_008a_judge_prime_number_by_trial_division.py