백준 1929 풀이

1929

소수 구하기

문제의 최초 접근 : 소수 특징 파악

I P O

I : 한줄에 띄어쓰기로 구분된 범위의 시작지점 , 끝나는 지점의 정수형 데이터

P : 입력받은 범위 안에서 소수 추출

O : 소수 (한줄에 한 소수)

source code

1. 입력받은 값 안에 어떤 소수가 있는지 확인

M,N = map(int , input().split())

for i in range (M , N + 1):
    print(i , "\n")
    for j in range (1 , i + 1):
        print("\t",j)

1. List z 에 1 ~ 나누어지는 피연산자 까지 추가한 후, 나머지를 값을 새로운 List value에 추가. 리스트의 크기가 2 이상인 경우 소수가 아님. 시간 초과

M,N = map(int , input().split())
z = []
value = []

for i in range (M , N + 1):
    for j in range (1 , i + 1):
        if i % j == 0:
            z.append(j)
    value.append(z)
    z = []

for k in range (len(value)):
    if len(value[k]) == 2:
        z.append(value[k][1])

[print(n) for n in z]

1. 소수의 특징에 접근. 특정 수를 2로 나누어도, 4로 나누어도 소수를 판정하는데는 똑같은 의미로 작용

• 나누어지는 특정수의 제곱근에 정수형 결과값, 나누는 수의 복잡도를 줄여줌.

import math

M,N = map(int , input().split())
z = []
value = []

for i in range (M , N + 1):
    if i == 3:
        z.append(3 % 2)
        value.append(z)
        print(3)
        z = []
    else:
        for j in range (2 , int(math.sqrt(i)) + 1):
            z.append(i % j)
        if 0 not in z:
            print(i)
        z = []

question Point

• 왜 2 ~ 제곱근 (1은 모든수를 나머지가 0으로 나눌 수 있는 수이기 때문) 값 까지의 나눗셈에 나머지를 구함으로 소수를 추출할 수 있는가?

-> 원래는 제곱근이 모든 나누어지는 수의 최소값 (즉 그 이상의 수는 2 ~ 제곱근의 배수)로 판단하여 가능하다고 생각했으나, 위 논리로는 나누는 수가 15일 때 7 과 같은 경우를 설명하지 못한다.