[백준/BOJ] - 1929번 python 풀이 - '에라토스테네스의 체'

---

Key Point

1. '에라토스테네스의 체'를 사용하면 해결되는 문제이다.

-> ex) 17이라면 해당 제곱근은 4.xx 즉 2부터 4까지 나눠가며 17이 나눠지는지 판별하는 것이다.

-> ex) 16이라면 해당 제곱근은 4, 16의 약수는 1 2 4 8 16 이다. 약수는 대칭을 이루는데 중간이 되는 지점은 해당 수의 제곱근을 포함한 제곱근 보다 작은 수 범위이다. 그렇기에 제곱근까지 판별하면 가능하다는 의미!

-> 2부터 판별하고 싶은 수의 제곱근 까지 해당수를 나눠가며 나눠지지 않을 경우 소수!

-> 나눠지면 약수가 3개이상(1,자기자신, 나눠 떨어지는 수)이므로 소수가 아님!

 

알게 된 문법

for i in arr[:]:

---

정답 코드

import sys
M,N = map(int,sys.stdin.readline().split())

for i in range(M, N+1):
    if i==1:
        continue
    for j in range(2,int(i**0.5) + 1):
        if i % j == 0:
            break
    else:
        print(i)

---

시간 초과

- for j in temp[:] 부분에서 반복문을 돌리며 index의 위치를 고정 시켜주기 위해 해당 문법을 사용해주었는데 

temp[:]가 리스트를 복사하는 과정이 있기 때문에 시간이 오래걸려 시간 초과가 된 듯 하다.

import sys
M,N = map(int,sys.stdin.readline().split())

result = []
temp = [i for i in range(2,N+1)]
#for i in temp:
while True:
    length = len(temp)
    if length == 0:
        break
    else:
        tem = temp[0]
        result.append(temp[0])

        for j in temp[:]:
            if j % tem == 0:
                temp.remove(j)
if M > 2:
    for i in result:
        if i > 2:
            print(i)
else:
    for i in result:
        print(i)

---

시간 초과

- 가장 무난하게 생각할 수 있는 코드이다. 1부터 자기 자신까지 반복문을 돌려가며 약수의 수가 2인 수를 출력하는 방식.

 

import sys

M,N = map(int,sys.stdin.readline().split())
cnt = 0
for i in range(M,N+1):
    for j in range(1,i+1):
        if i % j == 0:
            cnt+=1
    if cnt == 2:
        print(i)
    cnt = 0

---

시간 초과

- 나름 머리를 써서 2의 배수가 무조건 소수가 되지 않는다는 점을 이용하여 처음 반복문을 돌릴 때 2의 배수는 검사하지 않게끔 하였으나 이 또한 시간 복잡도 초과로 인해 실패

import sys

M,N = map(int,sys.stdin.readline().split())
cnt = 0
if M == 2 or M == 1:
    print(2)
if M % 2 != 0: #odd
    for i in range(M,N+1,2):
        for j in range(1,i+1):
            if i % j == 0:
                cnt+=1
        if cnt == 2:
            print(i)
        cnt = 0
else:
    for i in range(M+1,N+1,2):
        for j in range(1,i+1):
            if i % j == 0:
                cnt+=1
        if cnt == 2:
            print(i)
        cnt = 0