글 읽기 - [Python3] 형님들 한번만 도와주세요 (시간초과)

wnsfuf0121 5년 전 0

전 여기서 더 무엇을 해야할 지 모르겠습니다. C언어와 Java의 논리와 일치하는 것 같은데 언어의 한계인가요...? 여기서 좀 더 줄일 수 있는 방법 좀 알려주싶쇼 행님덜

import sys
s = sys.stdin.readline

input_min, input_max = list(map(int,s().split()))

input_list = []
for i in range(input_min,input_max+1) :
    input_list.append(i)

for i in range(len(input_list)) :
    check = 0
    if input_list[i] == 1:
        continue
    for j in range(2,input_list[i]) :
        if input_list[i] % j == 0 :
            check = 1
            break
    if check == 0 :
        print(input_list[i])

hello70825 5년 전 0

왠만하면 분류에 나온 유형이나 그것보다 효율적인 알고리즘으로 푸는게 좋습니다..

5.9초로 통과하는 코드를 보니 다음과 같이 만들었네요

이렇게 해도 시간 초과가 나오면 리스트 추가해주지 말고 바로 for문으로 시작해서 i 범위를 min,max+1로 잡으면 될 것 같습니다.

for i in range(len(input_list)):
    if input_list[i]!=1:
        check=0
        for j in range(2,input_list[i]):
            if input_list[i]%j==0:
                check=1
                break
        if check==0:
            print(input_list[i])

nova9128 5년 전 0

파이썬이 고급언어이지만 다른 언어에 비해 좀 느립니다.

다만 그렇기에 그걸을 최적화시켜 놓은 알고리즘 소스코드들이 많습니다.

당장에는 프로그래밍 실력 향상을 위해 직접 고민해보고 구현해보신후 조금 더 공부해보실기회가 되신다면

https://blog.naver.com/nova912...

여기에서 제가 공부하려고 소수문제만 모아두고 다른분들 소스코드랑도 속도 비교해놓은 것 있는데 참고하셔요.

소수 찾기[편집]

현재까지 알려진 가장 간단한 방법으로 에라토스테네스의 체가 있다. 방법은 다음과 같다.

찾고자 하는 범위의 자연수를 나열한다.
2부터 시작하여, 2의 배수를 지워나간다.
다음 소수의 배수를 모두 지운다.

이를 반복하여 마지막까지 지우면, 남는 수들이 소수가 된다. 이 과정은 사실 어떤 자연수

$n$ 이 소수임을 판정하기 위해서 $\lfloor {\sqrt {n}}\rfloor$ 까지만 진행하면 되는데^[1], 수가 수를 나누기 위해서는 그 몫이 항상 필요하며 나누는 수와 몫 중 어느 하나는 반드시 ${\sqrt {n}}$ 이하이기 때문이다.

소수를 골라내기 위한 방법은 다음과 같다. 이 방법을 이용해 소수를 어느 정도 골라낼 수 있다.

2와 5를 제외하면, 모든 소수의 일의 자리 수는 1, 3, 7, 9이다.
어떤 자연수 $n$ 이 소수임을 판정하기 위해선 ${\sqrt {n}}$ 까지의 수 중 1을 제외하고 그 자연수의 약수가 있는 지 확인하면 된다.
배수의 성질을 이용하면 쉽게 구할 수도 있다.

그 외에도 다양하고 복잡한 판정법이 존재하지만, 위의 세 가지는 당연하고 간단한 것들이다.

nova9128 5년 전 0

@wnsfuf0121

input_min,input_max=map(int,input().split())
input_list = []
for i in range(input_min,input_max+1) :
    input_list.append(i)
#처음에 이부분 만드실떄 짝수를 제외하고 홀수만 넣어서 만들면 속도가 2배로 빨라집니다.
if input_min%2==0:
    input_list = [i for i in range(input_min+1,input_max+1,2) ]
else:
    input_list = [i for i in range(input_min,input_max+1,2)]
#print(input_list)






#그리고 이 뒤부분은 매 숫자 1개씩마다 2 부터 input_list[i]까지 해서 시간초과 됩니다.
#이부분도 차라리 위에서 인풋리스트를 만들지 마시고 차라리 소수리스트를 한번만 만들어서 
#그안의 소수로만 나누어서 0되면 패스하고 0이 안되면 소수인걸로 판별하시면 훨씬 빨라질듯 보입니다.

for i in range(len(input_list)) :
    check = 0
    if input_list[i] == 1:
        continue
    for j in range(2,input_list[i]) :
        if input_list[i] % j == 0 :
            check = 1
            break
    if check == 0 :
        print(input_list[i])

wnsfuf0121 5년 전 0

답변 정말 감사드립니다. 현재 여러분들의 피드백을 받아 두개의 코딩을 시도하였는데, 둘 다 시간초과가 됩니다. 한번만 더 봐주시면 감사하겠습니다 ㅜㅜ

#1번
import sys
s = sys.stdin.readline

input_min, input_max = list(map(int,s().split()))
sosu_list = []

for i in range(input_min,input_max+1) :
    check = 0
    if i == 1:
        continue
    elif i == 2 :
        sosu_list.append(i)
    elif i % 2 != 0 :
        for j in range(len(sosu_list)) :
            if i%sosu_list[j] == 0 :
                check = 1
                break
        for j in range(2,i) :
            if i % j == 0 :
                check = 1
                break
        if check == 0 :
            sosu_list.append(i)

print(*sosu_list,sep='\n')



#2번
import sys
s = sys.stdin.readline

input_min, input_max = list(map(int,s().split()))

for i in range(input_min,input_max+1) :
    check = 0
    if i == 1:
        continue
    elif i == 2 :
        print(i)
    elif i % 2 != 0 :
        for j in range(2,i) :
            if i % j == 0 :
                check = 1
                break
        if check == 0 :
            print(i)

nova9128 5년 전 0

음 소수리스트를 따로 만들어야된다는것이 아래같은 방법이었습니다.^^

즐거운 코딩하세요~~

import sys
s = sys.stdin.readline

sosu_list = [3,5]

#어제 알려드린 이론 문제 제한조건 1,000,000이 소수인지판별하려면 루트(1,000,000)이하의 소수만 찾아서 비교하면 되겠죠???
#또한 두번째 팁 짝수 제거 그리고 5의 배수도 제거 그럼 1000이하의 소수는 금방 찾습니다.참고로 997이 소수이니 998까지만 돌렸습니다.

for i in range(7,998,2) :
    check = 0
    #if i == 1:
        #continue
    #elif i == 2 :
    if i%5!=0:
        for _ in sosu_list:
            if i%_==0:break
            else:check+=1
        if check==len(sosu_list):
            sosu_list.append(i)
sosu_list=[2]+sosu_list
### 이런식으로 일단 특정범위까지 소수리스트를 만들고서 시작합시다.




input_min, input_max = map(int,s().split())

###아까 만든 소수리스트로 처리가능할경우
if input_max<1003:
    for sosu in sosu_list:
        if sosu>=input_min  and sosu<=input_max:
            print(sosu)
        elif sosu>input_max:break
        
#추가적인 소수값을 찾아야할경우
else:
    if input_min<1000:
        for sosu in sosu_list:
            if sosu>=input_min:
                print(sosu)
    #1003이상의 소수찾기
        for i in range(1003,input_max+1,2):
            if i%5!=0:
                check=0
                for sosu in sosu_list:
                    if i%sosu==0:check=1;break
                if check==0:print(i)

    else:
        if input_min%2==0:input_min+=1
        for i in range(input_min,input_max+1,2):
            if i%5!=0:
                check=0
                for sosu in sosu_list:
                    if i%sosu==0:check=1;break
                if check==0:print(i)
    

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

문제

문제

출처

ICPC

[Python3] 형님들 한번만 도와주세요 (시간초과)

wnsfuf0121 5년 전 0

hello70825 5년 전 0

nova9128 5년 전 0

소수 찾기[편집]

nova9128 5년 전 0

wnsfuf0121 5년 전 0

nova9128 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말