[백준 1978번-파이썬/Python] 소수 찾기

http://acmicpc.net/problem/1978

{코드}

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

{설명}

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

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

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

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

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

{코드}

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

{설명}

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

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

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

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

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

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

---

걸리는 시간 - timeit 모듈을 사용하여 1000번 반복한 결과의 평균

	1차	2차	3차	4차
각각 확인	0.000251421366	0.000259796494	0.000256705552	0.000261093617
에라토스테네스	0.000209317954	0.000214768780	0.000208121491	0.000200455188

보기와 같이 에라토스테네스의 체를 활용한 결과가 더 빠르다는 것을 알 수 있습니다.

물론 항상 이런것은 아니고 범위가 커질수록 메모리를 많이 소모하니 해결하려는 문제에 맞게 사용하시기 바랍니다.