BOJ数学:小数を検索(1978)

問題の定義
自然数nが与えられると、nが素数であるか否かを判別する.
答えを出す.
時間複雑度はO(n)であり,2〜n−1の除算演算が必要であるためである.

import math

# 소수 판별 함수 (2이상의 자연수에 대해)
def is_prime_number(n):
    # 2부터 n-1까지의 모든 수를 확인하며
    for i in range(2, n):
        # x가 해당 수로 나누어 떨어진다면
        if n % i == 0:
            return False # 소수가 아님
    return True # 소수임

is_prime_number(153)

薬性

nの平方根を調べるだけです.
説明する.
時間複雑度はO(n^(1/2))であり,2からn−1までの平方根の除算演算が必要であるためである.

import math

# 소수 판별 함수 (2이상의 자연수에 대해)
def is_prime_number(n):
    # 2부터 x의 제곱근까지의 모든 수를 확인하며
    for i in range(2, int(math.sqrt(n))+1):
        # x가 해당 수로 나누어 떨어진다면
        if n % i == 0:
            return False # 소수가 아님
    return True # 소수임

is_prime_number(153)

エラトネスのボリュームアルゴリズム
これは

個の自然数を少数判別するための典型的なアルゴリズムである.

では、N以下のすべての小数を検索します.

において、テストステロンの体アルゴリズムの具体的な操作過程は以下の通りである.

2からNまでのすべての自然数をリストします.

処理されていない最小数iは、

の残りの数で検索される.

の残りの数からiのすべての倍数を除去する(iは除去しない).

これ以上繰り返されないまで、2回と3回のプロセスを繰り返します.
※nの平方根(5)を完成した数7,9,11…上記の手順では、繰り返しても更新されません.

は、残りのすべての水の未処理の最小水2の倍数を除去する.

import math

n = 100 # 2부터 100까지의 모든 수에 대해 소수 판별
# 처음엔 모든 수가 소수(True)인 것으로 초기화(0과 1은 제외)
array = [True for i in range(n+1)]

# 에라토스테네스의 체 알고리즘
# 2부터 n의 제곱근까지 모든 수에 대해서
for i in range(2, int(math.sqrt(n))+1):
    if array[i] == True: # 아직 처리되지 않은 가장 작은 소수
        j = 2 # X 2부터시작해서
        while i * j <= n: # 해당 소수의 배수를
            array[i*j] = False # 지워준다
            j += 1 # 다음 배수를 계산하기 위해 j를 증가시킨다.

# 모든 소수 출력
for i in range(2, n+1):
    if array[i]:
        print(i, end = ' ')