글 읽기 - 시간초과라고 뜨는데 이렇게 풀면 안되나여...

youngzzangs2 1년 전 0

코드 안 배끼고 스스로 만들려고 하니까 이렇게 노가다 권법밖에 안나오는데

도저히 안되서 인터넷 쳐보니 무슨무슨 체로 풀어야 한다고 나오더군요...

흑흑

혹시 이 상황에서 살짝 수정해서 시간초과라고 안 뜰 방법은 정녕 없을까요

m, n = map(int, input().split())
m_list = [] # 사이 수 담는 리스트
y_list = [] # 사이 수의 약수 개수 담는 리스트

# 사이 수 반복문 돌려서 담기
for i in range (m, n+1) :
  m_list.append(i)

# 약수 개수 함수 정의
def weneed(rn) :
    count = 0
    for i in range (1, rn+1) :
        if rn == i :
            count = count + 1
        elif rn % i == 0 :
            count = count + 1
    return count
                
# 사이 수의 각각 약수 개수 담기
for j in range (m, n+1) :
    y_list.append(weneed(j))
    
# 최종 소수 리스트 출력
for i in range (0, len(m_list)) :
    if y_list[i] == 2 :
        print(m_list[i])

pill27211 1년 전 1

말씀 하신데로 소수인지 하나하나 모두 판별 하기에는 N의 범위를 생각 했을 때 다소 무리가 있습니다.

"에라토스테네스의 체"는 소수 판별 문제에 있어서 굉장히 유용한 알고리즘이기 때문에 꼭 익혀 두시는 걸 추천 드립니다.

시간 복잡도 측면에서도

O(N^2) -> O(Nlog(logN))

로 차이가 어마어마 하지요.

youngzzangs2 1년 전 0

감사합니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과라고 뜨는데 이렇게 풀면 안되나여...

youngzzangs2 1년 전 0

pill27211 1년 전 1

youngzzangs2 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말