baekjoon(1929-소수 구하기)_python

1) 문제

1929번: 소수 구하기

2) 예시

 

3) 제출

import sys
input = sys.stdin.readline

m, n = map(int, input().split())
# 구한 소수 집어 넣을 리스트 선언
primeNum = []

def isPrime(x):
    # 1일 경우를 예외 처리
    if x <= 1:
        return False
    # 2일 경우부터 소수인지 판별
    for i in range(2, int((x ** (1/2)) + 1)):
        if x % (i) == 0:
            # 나누어 떨어지는 경우 = 소수
            return False
    # 소수로 판별나지 않고 for문을 빠져나온 경우 != 소수
    return True

# m이상 n이하의 모든 숫자를 isPrime 함수를 확인
for i in range(m, n + 1):
    if isPrime(i):
        primeNum.append(i)

for i in primeNum:
    print(i)

4) 메모리/시간/코드 길이

5) PLUS

3달 전에 했던 시간 초과 코드

import sys
input = sys.stdin.readline

m, n = map(int, input().split())
li = list(set(i for i in range(2, n + 1)))
g, cnt = 0, 0

for i in range(0, n):
    cnt = 0
    if i >= len(li) - 1:
        break
    if li[i] < m:
        g = i
    for k in range(i + 1, len(li)):
        if li[k - cnt] % li[i] == 0:
            li.pop(k - cnt)
            cnt += 1
        else :
            continue
        
sen = ""
for i in range(g + 1, len(li)):
    if li[i] > n:
        break
    else:
        sen += str(li[i]) + "\n"

print(sen)

0 ~ n까지 모든 반복문을 돌렸음

 

이것보다 

https://youtu.be/CyINCmJPjfM

를 보고 제곱근까지만 확인하면 된다는 것을 알았다

예를 들어 100의 소수를 구하려면 1~100을 확인하는 것이 아니라,

1 ~ 10( -> sqrt(100))까지만 확인해 주면 된다.

이게 얼마나 큰 차이인지 감이 안 잡힌다면

 

2500을 소수인지 확인하고 싶을 때,

숫자 1개를 집어 넣었을 때 1초가 걸린다고 하면,

1 ~ 2500을 확인하면, 2500초 ( 약 41분)이 걸리게 된다

이때 1~50을 확인하면 50초가 걸린다.