n以下の素数を求める方法

1. ブルートフォース法: ブルートフォース法は、最も基本的な素数判定法です。2から始めてnまでの各数に対して、その数が自身と1以外の数で割り切れるかどうかを調べます。割り切れる場合は素数ではないと判定します。

def is_prime(n):
    if n <= 1:
        return False
    for i in range(2, n):
        if n % i == 0:
            return False
    return True
def primes_up_to_n(n):
    primes = []
    for i in range(2, n+1):
        if is_prime(i):
            primes.append(i)
    return primes
n = 1000
prime_numbers = primes_up_to_n(n)
print(prime_numbers)

2. エラトステネスの篩: エラトステネスの篩は、効率的な素数判定法です。まず、2からnまでの数をリストに用意し、2から始めて倍数を順に取り除いていきます。最終的に残った数が素数となります。

def sieve_of_eratosthenes(n):
    primes = [True] * (n+1)
    primes[0] = primes[1] = False
    p = 2
    while p * p <= n:
        if primes[p]:
            for i in range(p * p, n+1, p):
                primes[i] = False
        p += 1
    prime_numbers = []
    for i in range(2, n+1):
        if primes[i]:
            prime_numbers.append(i)
    return prime_numbers
n = 1000
prime_numbers = sieve_of_eratosthenes(n)
print(prime_numbers)

これらの方法を使用すると、与えられた整数n以下の素数を見つけることができます。ブルートフォース法は単純ですが、nが大きい場合には効率が悪いです。一方、エラトステネスの篩は効率的であり、大きな範囲の素数を素早く見つけることができます。

素数探索には他にも様々なアルゴリズムが存在しますが、ここではブルートフォース法とエラトステネスの篩を紹介しました。これらのコード例を参考にして、自分自身で素数を求めるプログラムを作成してみてください。