특정 숫자가 소수인지 아닌지 판별하기 위해서는 2부터 해당 숫자-1까지의 숫자들로 나누어 나머지가 0인지 확인합니다. 또한 나머지가 0인지 여러 번 비교해야 하는데, 그 때마다 소수인지 아닌지 출력할 수 없으므로 그 중 한 번이라도 나머지가 0이 되면, 특정 변수의 값을 변경하고, 마지막에 그 변수의 값이 달라졌을 때는 소수가 아님을 출력하도록 코딩합니다. 그 변수의 값이 여전히 0일 때 그 숫자는 소수가 됩니다. #파이썬 #소수판별 #파이썬for문 #if문 #반복문 #로사쌤 #로사쌤의컴교실
중학교 1학년 교과과정의 시작은
소수를 찾는 것부터 시작합니다.
에라토스네스의 체를 이용하여 소수를
판별하는 법을 배우면서 2, 3, 5, 7, 11, ...로
이어지는 소수의 수열을 배웁니다.
오늘은 소수의 정의를 이용해서
파이썬으로 소수를 구별하는 코드를
만들어 보려 합니다.
여러분도 잘 아시다시피,
소수의 정의는
'1과 자기 자신 외에 양의 약수가 없는 1보다 큰 자연수'입니다.
따라서, 자연수 중에서 1은 소수가 아닙니다.
2부터 소수가 될 자격이 있는데,
6과 같은 수는 1, 2, 3, 6을 양의 약수로
갖기 때문에 소수가 아닙니다.
6을 예로 들어서 설명하면,
6을 2부터 자신보다 1이 작은 수들인
[2, 3, 4, 5]로 나누어 보면,
나머지는 [0, 0, 2, 1]이 됩니다.
결국, 자연수 6은 [1, 6] 이외에도 [2, 3]으로
나누어도 나머지가 0이 되기 때문에
소수가 아닙니다.
이번에는 자연수 5를 예로 들어보겠습니다.
5를 2부터 자신보다 1이 작은 수인
[2, 3, 4]로 나누어 보면,
나머지는 [1, 2, 1]이 됩니다.
자연수 5는 [1, 5] 이외에는 나누어도
나머지가 0이 되지 않기 때문에
[2, 3, 4]를 양의 약수로 갖지 않습니다.
따라서, 소수가 분명합니다.
1. 알고리즘을 파이썬으로 만들어 본다.
가끔 알고리즘 문제에 나오는 소수계산을 위해 정리하는 글이다.
소수란, 1과 자기 자신 이외에 약수를 가지지 않는 1보다 큰 자연수 이다.
1은 소수가 아니다
소수 판별 알고리즘은 대표적으로 두가지 방법으로 구현 할 수 있다.
일반적인 방법
우선, 반복문을 사용하는 것이다.
이 방법은 1개의 숫자가 소수인지 아닌지 판별하는데 사용하면 좋다.
여러 숫자를 소수 판별해야하는 경우는 아래 있는 에라토스테네스의 체가 더 유용하다.
n이라는 숫자가 소수인지 확인하기 위해서는 2부터 n-1까지 나눠보면서 나머지가 0이 나오는 숫자가 한개도 없으면 n은 소수이다.
하지만 n-1까지 나눠보지 않더고 √n 까지만 확인해봐도 된다.
소스코드import sys, math # 소수 판별 알고리즘 : 제곱근까지 구하기 def isPrime(x): if x == 1: # 1은 소수가 아님 return False for i in range(2, int(math.sqrt(x))+1): if x % i == 0: return False return True
다른 방법으로는 에라토스테네스의 체가 있다. 위의 방법과 비슷하지만, 소수 판별을 해야하는 숫자가 많을 때 유리하다.
왜냐하면 리스트에 2부터 n까지에 대해 소수 여부를 저장하기 때문에 한번 계산해두고, 해당 숫자가 소수인지 확인하는 것은 O(1)이 걸리기 때문이다.
단, 2부터 n까지의 소수 여부를 저장하는 배열이 필요하므로 그만큼 공간복잡도가 들어간다.
소스코드import sys, math target = 1000 # 구하려는 값의 범위 #에라토스테네스의 체 prime = [True]*(target) prime[1] = False # 1은 소수가 아님 m = int(math.sqrt(target)) for i in range(2, m+1): if prime[i] == True: for j in range(i+i, target, i): prime[j] = False
소수(Prime number)는 1과 자기자신만을 약수로 가지는 양의 정수를 말한다. 2, 3, 5, 7, 11, 13... 등의 수이다. 어떤 수가 소수인지 판단하는 방법에 대해 알아보자.
가장 간단하게 소수의 정의로부터, 어떤 자연수 N이 소수인지를 살펴보려면
- N 이 1 이면 소수가 아니다.
- 2 부터 N-1 까지의 자연수들로 순서대로 N을 나눠서 나누어 떨어지는 수가 하나도 없으면 N은 소수이다.
라는 간단한 검사 규칙을 얻을 수 있다.
기본적으로 이 규칙을 그대로 적용하여 코드로 옮겨보면 생각보다 매우 간단한 함수가 만들어진다.
def is_prime_bad(n: int) -> bool: if n < 2: return False for i in range(2, n): if n % i is 0: return False return True이 함수의 문제는 이름에서 알 수 있듯이, 그 성능이 매우 나쁘다는 점이다. 120 미만의 소수를 모두 찾아보면
for i in range(120): if is_prime_bad(i): print(i)제법 빠르게(?) 답을 구해주는 것 같다. 그렇지만 10만 이하에는 몇 개의 소수가 있는지 세어보는 건 어떨까?
%time len([x for x in range(1, 100000) if is_prime_bad(x)]) # Wall time: 39.9 s # 9592거의 40초 가까이되는 시간이 걸렸다. 만약 "2백만 이하의 소수의 합을 구하라"는 문제를 풀려고 한다면, 제 아무리 좋은 성능의 컴퓨터를 쓰더라도 매우 긴 시간이 걸릴 수 있다.
이 함수의 효율을 좀 더 높일 방법은 없을까? 소수의 성질에 대해서 조금 더 살펴보자. 소수는 1과 자기 자신 이외에는 약수를 가지지 않는다고 하였다. 그래서 2를 제외한 모든 짝수는 2로 나눠지므로 소수가 아니다. 이 성질을 이용하면 검사해야 하는 개수를 반으로 줄일 수 있다.
def is_prime_bad_too(n: int) -> bool: if n < 2: return False if n == 2: return True if n % 2 is 0: return False for i in range(3, n, 2): if n % i is 0: return False return True그래서 테스트를 해보면,
대략 절반으로 줄였다. 하지만 이 마저도 그리 좋은 성능은 아니다. 좀 더 좋은 방법이 없을까? 만약 어떤 자연수 N이 a로 나눠진다면 N = a * b 로 표현할 수 있을 것이다. 그렇다면 N 은 a 로도 b 로도 나눠진다는 말이다. 즉 이 말은 N의 제곱근 r 을 기준으로 곱해서 N이 될 수 있는 약수들이 같은 개수로 분포한다는 말이다. 따라서 N이 소수인지를 알고 싶으면 N의 제곱근까지만 검사해보면 된다. 이 룰을 추가하는 것만으로 엄청난 시간을 줄일 수 있다.
def is_prime_not_bad(n: int) -> bool: if n < 2: return False if n is 2: return True if n % 2 is 0: return False l = round(n ** 0.5) + 1 for i in range(3, l, 2): if n % i is 0: return False return True테스트를 해보자
%time len([x for x in range(1, 100000) if is_prime_not_bad(x)]) # Wall time: 276 ms # 9592거의 100배나 빨라졌다!!!!
조금 더 다듬어 보자. 몇 가지 트릭을 추가한다.
- 10미만의 작은 소수들은 2나 3으로만 나눠지지 않으면 된다.
- 그 이상의 수들에 대해서는 5, 7, 9, 11, 13, 15... 등의 홀수로 나눠보면 된다. 하지만 이미 3의 배수에 대해서는 1에서 검사하기 때문에 5, 7, 11, 15,... 의 패턴으로 검사할 수 있다.
이를 이용해서 최적화한 코드는 다음과 같다. 이 코드는 실제로 프로젝트 오일러의 많은 소수 관련 문제를 풀 때 사용한 함수이다.
def is_prime(n: int) -> bool: if n < 2: return False if n in (2, 3): return True if n % 2 is 0 or n % 3 is 0: return False if n < 9: return True k, l = 5, n**0.5 while k <= l: if n % k is 0 or n % (k+2) is 0: return False k += 6 return True이 함수를 이용해서 10만 이하의 소수의 개수를 세어보면
%timeit len([x for x in range(1, 100000) if is_prime(x)]) # 169 ms ± 3.47 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)앞서 작성했던 제법 괜찮은 함수보다도 30%이상 빨라졌다. 이 함수를 써서 1백만 이하의 소수의 개수를 세어보면 약 4초 가량이 걸린다.
만약 처음에 소개한 가장 나쁜(?) 성능의 코드를 C로 동일하게 구현하여 1백만 이하의 소수의 개수를 세면 시간이 얼마나 걸릴까?
$ time ./p.exe 78498 real 2m14.804s user 0m0.015s sys 0m0.000s무려 2분 14.8초가 걸렸다.
부록 : 에라토스테네스의 체
에라토스테네스의 체는 소수의 계산을 조금 더 편하게 하는 방법으로 2부터 시작하는 연속된 자연수를 미리 써 두고, 처음 나타나는 수의 배수들을 모두 지우는 식으로 나아가서 소수만 남기는 방식으로 구한다. 이 방식은 미리 소수가 나타날 범위를 한정해야 한다는 단점이 있지만, 구현도 그렇게 어렵지 않고, 성능도 매우 좋다.
for i in range(120): if is_prime_bad(i): print(i) 0이를 이용해서 10만 이하의 소수의 개수를 세면?
for i in range(120): if is_prime_bad(i): print(i) 1근데 이 방법도 더 효율적으로 개선할 수 있다. 그것은 바로 파이썬의 슬라이스 문법을 이용한 치환이다. 파이썬의 슬라이스 문법을 이용하면 특정 범위와 스텝을 통해 구간을 정할 수 있다. 이를 이용해서 리스트 내의 불연속적인 부분집합을 매우 빠르게 치환할 수 있다. 그리고 이 치환 동작은 파이썬 처리 로직이 아닌 C 레벨에서 처리되기 때문에 매우 빠르다.