백준 1929번, math.sqrt()

문제

https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

나의 풀이

import math
a,b=map(int,input().split())

def checknumber(n):
	if n==1:
		return False
	for j in range(2,int(math.sqrt(n))+1):
		if i%j==0:
			return False
	return True

for i in range(a,b+1):
	if checknumber(i):
		print(i)

처음에 checknumber 함수에서 for문을 2부터 n까지의 값을 나누어서 계산한 탓에 시간초과가 걸리게 되었다. 소수를 구하기 위해서는 2부터 n의 제곱근까지만 나누어주어도 되었고 따라서 그렇게 계산한 결과 시간초과의 문제는 해결하게 되었다.

두 번째 오답은 1이 소수가 아니라는 것을 간과해서 문제를 틀리게 되었고 앞으로 문제를 좀 더 잘 확인해야겠다.

여기서 사용한 math.sqrt(n)는 n의 값을 제곱근으로 바꾸어 float값으로 반환해주는 함수로 sqrt 대신 n**0.5도 같은 값이 나오게 된다.

 

다른 사람의 풀이

m,n = map(int,input().split())
prime = [1]*(n+1)
prime[0] = 0
prime[1] = 1
for i in range(2,n+1):
    if i>=m and prime[i]:
        print(i)
    if prime[i]:
        for j in range(2*i,n+1,i):
            prime[j] = 0

새로운 접근이었다. prime[]이라는 리스트에 그 숫자가 소수인지 아닌지를 1과 0을 이용해서 True False 값이 나오도록 이용하였고 작은 숫자부터 시작해 작은 숫자에 어떤 값을 곱한 값은 소수가 아닐 것이므로 그 값을 False 값이 나오도록 0을 대입해주면서 이미 지나친 소수가 아닌 값은 if문을 이용해 불필요한 계산을 줄일 수 있게 하였다.

 

그 결과 나의 코드의 풀이보다 6배나 빠른 처리를 보였으며 앞으로 이런 좀 더 수학적인 풀이를 할 수 있어야겠다.