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

http://acmicpc.net/problem/1929

{코드}

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

{설명}

소수란 1과 자기 자신으로만 나누어지는 숫자로 대표적으로 2, 3, 5, 7등이 있습니다.

또한 모든 숫자는 그 제곱근을 기준으로 약수의 절반이 각각 제곱근의 양옆에 위치하게 된다. (예, 16인 경우 1, 2, 4, 8, 16)

그러므로 각 수마다 2부터(1은 어차피 약수이며 1은 소수가 아니다) 그 수의 제곱근(포함해야 한다-16의 경우 4도 약수이다)까지 반복해

만약 그 수가 나누어지면 소수가 아니고 제곱근까지 반복했음에도 나뉘어지지 않았다면 소수이다.

*math 라이브러리의 sqrt함수가 있지만 루트 연산은 시간이 오래걸리기 때문에 i*i를 사용한다.

하지만 이 방법은 메모리는 비교적 적게 사용할지는 몰라도 시간이 굉장히 오래 걸리게 됩니다.

{코드}

sieve = [True]*1000001
sieve[0], sieve[1] = [False]*2
i = 2
while i <= 1000000:
  if sieve[i]:
    for t in range(i+i, 1000001, i):
      if sieve[t]:
        sieve[t] = False
  i += 1
m, n = map(int, input().split())
for i in range(m, n+1):
	if sieve[i]:
		print(i)

{설명}

이 방법은 에라토스테네스의 체를 이용한 방식으로 주어진 범위 안의 모든 수에 대해 소수를 판별하여

입력받은 수가 소수인지 아닌지 미리 구한 체를 통해 알아내는 방식이다.

에라토스테네스의 체는 2부터 n까지 돌면서 각 수의 배수를 지워나가는 방식이다.

예를 들어 2인 경우 2를 제외한 2의 배수들, 3인 경우 3을 제외한 3의 배수들을 지워나간다.

이와 같이 반복하며 이미 지워진 수의 경우 제외 연산을 하지 않는다. (예: 15의 경우에는 이미 3일 때 모두 지워졌다)

*range 함수는 range(시작, 끝+1, 증감)으로 증감에 넘긴 수를 시작에 더한다.

이 방식을 사용하면 메모리는 비교적 더 많이 사용하지만 시간은 훨씬 더 빨라진다.

메모리 소모를 줄여보려고 체의 범위를 n에 맞춰서 계산해보기도 하였으나

실행시간이 늘어나 결국 위의 방식이 더 낫다고 판단하였다.