Help us understand the problem. What is going on with this article?

Pythonで素数列挙と素数判定

More than 3 years have passed since last update.

たまに自分で使うので、Qiitaに投稿しておきます(´・ω・`)

primes(x)x未満の素数をリストに格納するメソッドです。アルゴリズムとしては定番の「エラトステネスのふるい」を利用しています。filter等を利用していない点が工夫といえると思います。

次にis_prime(x)は整数xが素数かどうかを判定するメソッドです。アルゴリズムはやはり定番の「ためし割り」。ただし疑似素数(2でも3でも5でも割り切れない数字)を利用することで、効率化を図っています。

import math

# 0以上整数x「未満」の素数をリストに格納して返す
def primes(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0 # 1は素数ではない

    # エラトステネスのふるい
    for prime in primes:
        if prime > math.sqrt(x): break
        if prime == 0: continue
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0

    return [prime for prime in primes if prime != 0]


# 整数xが素数かどうかを判定する
def is_prime(x):
    if x < 2: return False # 2未満に素数はない
    if x == 2 or x == 3 or x == 5: return True # 2,3,5は素数
    if x % 2 == 0 or x % 3 == 0 or x % 5 == 0: return False # 2,3,5の倍数は合成数

    # ためし割り: 疑似素数(2でも3でも5でも割り切れない数字)で次々に割っていく
    prime = 7
    step = 4
    while prime <= math.sqrt(x):
        if x % prime == 0: return False

        prime += step
        step = 6 - step

    return True


if __name__ == '__main__':
    print(primes(30)) #=> [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

    ls = [x for x in range(30) if is_prime(x)]
    print(ls) #=> [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

neko_the_shadow
IT業界の片隅でひっそり生きるシステムエンジニアです(´・ω・`)
https://nekotheshadow.github.io/
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした