[백준] 1929번 소수 구하기 - 파이썬

www.acmicpc.net/problem/1929

1929번: 소수 구하기

m ,n = map(int,input().split())


for i in range(m,n+1):
    num = 2
    while i != 1:
        if i % num==0 and i // num==1:
            print(i)
            break
        elif i % num!=0:
            num+=1
        elif i %num ==0:
            break

시간초과?시간초과?시간초과?시간초과?시간초과?시간초과?시간초과?시간초과?

소수 찾는 거 시간초과 오바다 진짜 ㅋㅋㅋㅋ

반복문 두개 동시에  써서 그런거 같은데 하나로 줄여봐야겠다.

def isprime(a):
    if a== 1:
        return False
    else:
        for i in range(2,int(a**0.5)+1):
            if a%i ==0:
                return False
        return True


m ,n = map(int,input().split())

for i in range(m,n+1):
    if isprime(i):
        print(i)

 

blog.naver.com/wndud5570/222194990247

백준 1929번: 소수 구하기(with 파이썬/에라토스테네스의 체)

이분거 참고함 ..

에라토스테네스의 체 자주 이용하자 소수는 이거 말고 없다 아직

 

에라토스테네스의 체는 

2부터 n 까지의 모든 자연수를 나열한후

남은 수중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다.

남은 수중에서 i의 배수를 모두 제거한다.

이 과정을 반복한다.