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

Konseo·2023년 8월 3일
0

알고리즘

목록 보기
4/21

개념

소수

  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=' ')

소수 판별 관련 문제

profile
둔한 붓이 총명함을 이긴다

0개의 댓글