입력받은 정수 n이 소수(Prime Number)인지 아닌지를 판별하는 방법
방법 1
for문을 돌리면서 1부터 n까지를 k에 넣고 n이 k로 나누어 떨어지는 경우에 cnt를 1씩 증가시킨다.
for문이 종료되었을 때 cnt 값이 2일 경우 소수이고 아닐 경우 소수가 아님
def prime(number):
cnt = 0
for n in range(1,number+1):
if number % n == 0:
cnt += 1
if cnt == 2:
return 1
else:
return 0
def is_prime(n):
for k in range(2,n):
# 2부터 n-1까지 나누어지지 않는 것만 확인하므로 더 간결한 코드임
if n % k == 0:
return 0
return 1
방법 2 : 빠르게 소수를 판별하는 방법
약수의 대칭성을 활용하면 방법 1보다 2배 빠르게 소수를 판별해 낼 수 있다.
예1) 16의 약수 : 1, 2, 4, 8, 16
16 = 1 x 16 = 2 x 8 = 4 x 4 = 8 x 2 = 16 x 1
sqrt(16) = 4를 기준으로 약수를 두 부분으로 구분하고, 16을 앞부분으로 나누면 뒷부분이 나오고 뒷부분으로 나누면 앞부분이 나오므로
앞부분을 확인했을 때 약수가 없으면 뒷부분에서도 약수가 없다.
예2) 30의 약수 : 1, 2, 3, 5, 6, 10, 15, 30
30 = 1 x 30 = 2 x 15 = 3 x 10 = 5 x6 = 6 x 5 = 10 x 3 = 15 x 2 = 30 x 1
sqrt(30) = 5.xx를 기준으로 약수를 두 부분으로 구분하고, 30을 앞부분으로 나누면 뒷부분이 나오고 뒷부분으로 나누면 앞부분이 나오므로
앞부분을 확인했을 때 약수가 없으면 뒷부분에서도 약수가 없다.
import math
def is_prime(n):
for k in range(2, int(math.sqrt(n))+1):
if n % k == 0:
return 0
return 1
에라토스테네스의 체
단일 수의 소수 여부는 O(sqrt(n))의 시간으로 구할 수 있는 반면, 대량의 숫자들의 소수 여부를 판별하려면 많은 시간이 걸리기 때문에 에라토스테네서의 체 알고리즘을 활용하면 소수들을 대량으로 빠르게 구할 수 있다.
https://upload.wikimedia.org/wikipedia/commons/b/b9/Sieve_of_Eratosthenes_animation.gif
원리
1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다.
2. 2는 소수이므로 2를 소수에 추가하고, 2를 제외한 2의 배수들을 모두 지운다.
3. 남아있는 수 가운데 3은 소수이므로 3을 소수에 추가하고, 3을 제외한 3의 배수들을 모두 지운다.
4. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.
tip : 구하고자 하는 숫자들의 범위가 2부터 120까지라고 할 때,
만약 단일 숫자 120이 소수인지 아닌지를 판별하고자 할 경우 sqrt(120) = 10.xx -> 11까지만 확인하면 되므로 120보다 작은 수의 경우에도 11보다 작은 수의 배수들만 지워도 된다!
def prime_list(n):
# 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주)
sieve = [True] * n
# n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(n)까지 검사
m = int(n ** 0.5)
for i in range(2, m + 1):
if sieve[i] == True: # i가 소수인 경우
for j in range(i+i, n, i): # i이후 i의 배수들을 False 판정
sieve[j] = False
# 소수 목록 산출
return [i for i in range(2, n) if sieve[i] == True]참조 : 위키백과-에라토스테네스의 체
boj_1644 : 소수의 연속합
입력
첫째 줄에 자연수 N이 주어진다. (1<= N <= 4,000,000)
출력
첫째 줄에 자연수 N을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력한다.
풀이 : 에라토스테네스의 체 + 투 포인터
def prime_list(n):
sieve = [True] * (n+1)
m = int(n ** 0.5)
for i in range(2, m + 1):
if sieve[i] == True:
for j in range(i+i, n+1, i):
sieve[j] = False
return [i for i in range(2, n+1) if sieve[i] == True]
import sys
n = int(sys.stdin.readline())
prime = prime_list(n); result = 0
i = 0; j = 0; value = prime[0] if prime else -1
while i < len(prime)-1:
while n > value:
j += 1; value += prime[j]
if n == value:
result += 1; j += 1; value += prime[j]
while value > n:
value -= prime[i]; i += 1
if n == value:
result += 1; value -= prime[i]; i += 1
print(result) if n != 2 else print(1)