白俊派森1929号.

https://www.acmicpc.net/problem/1929

少数を求める方法を理解してみましょう.

1.Nの平方根

一部の自然数はその自然数の2つの約数の積で表すことができる.12を例にとります.
12 =
1 x 12 =
2 x 6 =
3 x 4 =
4 x 3 =
6 x 2 =
12 x 1
すなわち、自然数を2つの約数の積として表すと、1つの約数は平方根より小さく、もう1つの約数は平方根より大きくなる.
(ただし、薬水a,bが異なる場合)
したがって、ある数が与えられたときにその数が小数であるかどうかを知りたい場合は、2からその数より小さい平方根またはその数に等しい自然数で除算すると、残りはゼロではない.
書くのはちょっと難しい...コードを見て

import math
import sys

def is_prime(num: int) -> bool:
    if num == 1:
        return False
    # 2부터 제곱근보다 작거나 같은 수까지 나누어보기
    for j in range(2, int(math.sqrt(num)) + 1):
    	# 나누었는데 나머지가 0이다? => 소수가 아니다
        if num % j == 0:
            return False
    # 다 나누었는데 나머지가 0인적이 없으면 소수
    return True


m, n = map(int, input().split())
#반복문으로 소수 판별 실행
for i in range(m, n+1):
    if is_prime(i):
        sys.stdout.write(str(i) + '\n')

このコードは、チェックする数値ごとに2から平方根未満または等分演算を行うため、チェックする数値が大きいほど、文を繰り返す演算が多くなります.
運行時間を短縮する方法はありますか?

2.エラトステネスの体

上図に示すように、プロセスは以下の通りです.

まず、2の倍数をクリアします。

クリアされた後、残りの数の最小の倍数をクリアします。(2の倍数が完了すると、3が行われます。)

これらを繰り返します。

import sys
import math

MAXNUM = 1_000_000


def is_prime(first: int, end: int):
	
    # 소수를 기록하는 check배열. True면 소수다.
    # 0, 1은 False로 초기화
    check = [False, False] + [True] * MAXNUM
    
    # 2부터 시작해서 배수 소거
    for i in range(2, int(math.sqrt(MAXNUM)) + 1):
        if check[i]: 	
            #
            cnt = 2
            while cnt * i <= end:
                check[cnt * i] = False
                cnt += 1
    # 출력
    for j in range(first, end + 1):
        if check[j]:
            sys.stdout.write(str(j) + '\n')


m, n = map(int, input().split())
is_prime(m, n)

実行時間が方法1よりかなり短縮されていることが分かる.
倍数をクリアするたびに、
減るから.