[백준 2581번-파이썬/Python] 소수

http://acmicpc.net/problem/2581

{코드}

def isPrime(n):
	if n <= 1:
		return False
	i = 2
	while i*i <= n:
		if n%i == 0:
			return False
		i += 1
	return True
sum, min = 0, 0
for n in range(int(input()), int(input())+1):
	if isPrime(n):
		if min == 0:
			min = n
		sum += n
if sum == 0:
	print(-1)
else:
	print(sum)
	print(min)

{설명}

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

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

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

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

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

{코드}

sieve = [True]*10001
sieve[0], sieve[1] = [False]*2
i = 2
while i <= 10000:
	if sieve[i]:
		for t in range(i+i, 10001, i):
			if sieve[t]:
				sieve[t] = False
	i += 1
sum, min = 0, 0
for n in range(int(input()), int(input())+1):
	if sieve[n]:
		if min == 0:
			min = n
		sum += n
if sum == 0:
	print(-1)
else:
	print(sum)
	print(min)

{설명}

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

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

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

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

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

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

---

각 방식이 걸리는 시간에 대해 보고 싶으시면 아래 글을 참고하세요.

2020/12/17 - [알고리즘 공부/BOJ백준 풀이] - [백준 1978번-파이썬/Python] 소수 찾기