소수와 에라토스테네스의 체

개념

소수

1. prime number
2. 1과 자기자신 외에는 어떠한 수로도 나누어 떨어지지 않는 수
3. 특정 수 N이 소수인지 아닌지 구하는 법
   • 2부터 n-1까지의 수로 해당 수를 나눠보고, 이 과정에서 어떠한 수에 의해 나누어 떨어지는 지 확인
     • 나누어 떨어진다면 합성수, 한 번도 나누어 떨어지지 않았다면 소수

코드로 표현하기

1. 소수를 찾는 함수 구현 (기본)

   def isPrime(a):
   	for i in range(2,a):
   		if n%i==0:
   			return False
   	return True

   • 위 방식은 입력값으로는 숫자 a에 대하여 2부터 a-1번까지, 즉 a-2번의 연산이 필요하다
     • 시간복잡도 O(x)

시간복잡도 줄이기

1. 약수의 특성을 활용해서 연산 횟수를 반으로 줄일 수 있다.

2. 약수의 특성

   • 특정 수 N의 약수들을 일렬로 나열했을 때 그 중 가운데의 수를 중심으로 약수가 대칭 된다.
   • 예시
     • 16의 약수를 일렬로 나열하면 1, 2, 4, 8, 16 이다.
     • 중간값인 4를 기준으로 양 옆을 보면 약수들이 서로 대칭되고 있음을 확인할 수 있다.
       • 116 == 161, 28 == 82
   • 다시 말해 우리가 만약 16의 약수를 찾고 싶다면 16의 약수 중간값을 기준으로 한 쪽만 검사를 하더라도 다른 쪽의 약수들을 알 수 있다.
   • 그렇다면 가장 먼저 중간값은 어떻게 계산할 수 있을까?
     • 일단 찾고자하는 수의 제곱근값으로 중간값을 가정할 수 있으며, 이 제곱근 값을 기준으로 왼쪽에 약수가 하나도 존재하지 않는다면, 제곱근 값 기준 오른쪽에도 약수가 존재하지 않는다고 확신할 수 있다. (좌우 대칭이라고 하였으므로)

3. 따라서, 우리는 기존 for문이 2에서 a-1까지 반복했던 것을 2에서 a의 제곱근까지만 돌도록 처리해주어 연산 횟수를 절반에 가깝게 줄여줄 수 있다.

4. 연산 횟수를 반으로 줄이는 코드

   import math
   
   def isPrime(a):
   	for i in range(2,int(math.sqrt(a))+1): #a의 제곱근을 정수화 한 후 +1
   		if n%i == 0:
   			return False
   	return True

   • 단순히 반복문의 범위만 절반으로 줄이는 것으로 쉽게 구현할 수 있다.
   • 시간복잡도 : O(x/2)

에라토스테네스의 체

여러 개의 수에 대하여 소수 판별을 해주어야 하는 상황이라면 어떨까. 100 ~ 300 사이의 모든 소수를 구해야하는 상황이라면 우리는 위의 방식을 이용해 하나하나 모든 수를 판별해줘야할까?

1. 에라토스테네스의 체 방식이란?

   1. 2~N까지의 범위가 담긴 배열을 만든다.
   2. 해당 배열 내의 가장 작은 수 i 부터 시작하여, i의 배수들을 해당 배열에서 지워준다.
   3. 주어진 범위 내에서 i의 배수가 모두 지워지면 i 다음으로 작은 수의 배수를 같은 방식으로 배열에서 지워준다.
   4. 더 이상 반복할 수 없을 때까지 2, 3번의 과정을 반복한다.

2. 에라토스테네스의 체 방식으로 코드 구현

   def isPrime(n):
   	arr=[True]*(n+1) # 특정 수가 지워졌는지 아닌지 확인하기 위한 배열
   	arr[0]=False # 인덱스 0은 단순히 인덱스와 특정 수의 값을 맞춰주기 위함
   	arr[1]=False # 소수는 2부터 시작
   	
   	for i in range(2,n+1):
   		if arr[i] == True :
   			j=2
   			while (i*j) <=n:
   				arr[i*j]=False
   				j+=1
   	return arr
   
   arr = isPrime(50) # 0~50 사이의 소수 배열을 구하기 위한 함수
   
   for i in range(len(arr)):
   	if(arr[i]==True:
   		print(i,end=' ')

   • 시간복잡도 : 상수시간과 가까울 정도로 빠른 시간 내에 연산이 가능하다.

에라토스테네스의 체 시간복잡도 줄이기

import math

def isPrime(n):
	arr=[True]*(n+1) # 특정 수가 지워졌는지 아닌지 확인하기 위한 배열
	arr[0]=False # 인덱스 0은 단순히 인덱스와 특정 수의 값을 맞춰주기 위함
	arr[1]=False # 소수는 2부터 시작
	
	for i in range(2,int(math.sqrt(n))+1): # 이 부분만 바뀜
		if arr[i] == True :
			j=2
			while (i*j) <=n:
				arr[i*j]=False
				j+=1
	return arr

arr = isPrime(50) # 0~50 사이의 소수 배열을 구하기 위한 함수

for i in range(len(arr)):
	if(arr[i]==True:
		print(i,end=' ')

소수 판별 관련 문제

• [백준] 소수 2581번 - https://www.acmicpc.net/problem/2581
• (+) [백준] 1929번 소수 구하기 - https://www.acmicpc.net/problem/1929
• (+) [백준] 4948번 베르트랑 공준 -  https://www.acmicpc.net/problem/4948