0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

Python3で任意の範囲の整数の中の素数を全て求める。

Posted at

こんにちは。今回もPythonのお勉強 問題集というサイトの問題を解いてみたので、知識の整理を兼ねてアウトプットしたいと思います。
今回は、任意の範囲の整数の中の素数を全て求める問題です。
#素数を求める
整数はその平方根よりも大きい素数では割ることができないという性質があります。今回はこの性質を利用していきます。

exmple.py
import math


prime_number_list = list()

def prime_number(start, end):
    for i in range(start, end+1):
        prime = True
        if i == 1:
            prime = False
        for j in range(2, math.floor(math.sqrt(i))+1):
            if i%j == 0:
               prime = False
               break
        if prime:
            prime_number_list.append(i)

    return prime_number_list

print(prime_number(2, 1000))

math.sqrtを利用してiの平方根を算出し、j(2~√i+1の間の整数)でiを割ることでiが素数か否かを判定し、primeをTrue or Falseにします。prime=Trueのときにiは素数なので、prime_number_listにappendします。
iが1のときに関しては、iが素数と判定されると困る(1は2以上の整数で割り切れないため、prime=Trueと判定されてしまうから)ので、強制的にprime=Falseとセットしています。
###偶数を除外して処理スピードを速くする
一つ目のforループの時点で偶数を除外したいと思います。ただし、2は素数なので、startが1 or 2のときに2が素数になるようにセットしています。

exmple.py
import math

prime_number_list = list()

def prime_number(start, end):

    ##追加
    if start < 3:
        prime_number_list.append(2)
    if start % 2 == 0:
        start = start + 1
    else:
        start = start

    ##1つずつスキップしてrangeを設定
    for i in range(start, end+1, 2):
        prime = True
        if i == 1:
            prime = False
            continue
        for j in range(2, math.floor(math.sqrt(i))+1):
            if i%j == 0:
                prime = False
                break
        if prime:
            prime_number_list.append(i)
    return prime_number_list

print(prime_number(1, 1000))

#おわりに
偶数を飛ばすときに2を素数判定させるのが冗長になってしまったので、そこを改善したいです。なにか意見があればコメントよろしくお願いいたします!

0
0
1

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?