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

素数の列挙

概要

素数の列挙に関しては多くのアルゴリズムが考案されていますが、ある自然数が自身以下の素数で割り切れるかを判定することで素数判定を行う実装例を記載します。ナイーブな実装なのでそれなりに低速ですが、大体10^5以下の素数であればこれで列挙できるかと思います。

実装例

# 自然数m以下の素数を返す
def prime_numbers(m):
    # 素数を保持するset
    primes = set()

    # 2以上m以下の素数を数え上げる
    n = 2
    while n <= m:
        # 自身より小さい全ての素数で割り切れなければ、素数とみなせる
        if all(n % i != 0 for i in primes):
            primes.add(n)
        n += 1

    return primes

実行結果

# m = 100の場合
{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97}

参考

素数列挙について
最速の素数列挙プログラム C#
https://projecteuler.net/problem=7

Why do not you register as a user and use Qiita more conveniently?
  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
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