[ 백준 1929 ] 소수 구하기

문제

 

 

 

처음 코드

m, n = map(int, input().split())
prime = []
for i in range(m,n+1):
    isPrime = 0
    for j in range(2,i):
        if i % j ==0:
            isPrime = 0
            break
        else:
            isPrime = 1
    if isPrime == 1:
        prime.append(i)
for x in prime:
    print(x)

시간 초과 에러가 떴다.

그래서 j를 2, (i//2)+1을 돌렸지만

이것 또한 시간 초과 에러가 떴다.

 

 

다른 사람들의 코드를 참고한 결과

소수를 구할때는 값을 2로 나눠서 거기까지 돌리는 것보다 제곱근으로 계산하는 것이 효율적이라는 것을 알게 되었다

 

 

 

 

* 알아둘 기본 개념

16의 제곱근은 4

10의 제곱근은 루트 10

 

 

 

1. 직접 제곱근을 계산하기

number**0.5로 제곱근을 계산할 수 있다.

 

 

2. math.sqrt()

import math를 한 후에

math.sqrt(100) 으로 제곱근을 구한다

 

 

나는 1번을 이용했다.

 

 

맞은 코드

m, n = map(int, input().split())
def isPrime(i):
    if i == 1:
        return False
    else:
        for j in range(2,int(i**0.5)+1):
            if i % j == 0:
                return False
        return True
        
for i in range(m,n+1):
    if isPrime(i):
        print(i)