<이코테> 코테에서 자주 출제되는 기타 알고리즘

1. 소수

소수란? 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나누어떨어지지 않는 자연수이다.

소수 판별 알고리즘 코드

def is_prime_num(x):
  for i in range(2, x): ##2~x-1까지 확인
    if x % i == 0 :
      return False
  return True


print(is_prime_num(12))

위 코드를 이용해 2~n씩 돌면서 코드를 확인한다.

 

위 코드를 개선시켜 시간을 더 줄여보자.

16이 소수인지 판단하기 위해선 위 코드로 구현하면 15부터 2까지 모두 나눠야한다. 하지만, 2*8이나 8*2 값이 같다는 것을 우린 알고 있지 않은가.

그래서 절반만 소수를 판단하여도 판별이 가능하다.

 

import math
def is_prime_num(x):
  for i in range(2,int(math.sqrt(x))+1) :
  
    if x % i == 0 :
      print(x,"  ", i, x%i)
      return False
  
  return True


print(is_prime_num(12))

이렇게 제곱근 +1만큼만 반복문을 돌려주면 더욱 빠르게 구현 가능하다.

 

  다수의 소수 판별 <에라토스테네스의 체 알고리즘>

특정한 수의 범위 안에 존재하는 모든 소수를 찾아보자.

import math

n = 1000
#모든 수가 소수(True)로 초기화(0과 1은 제외)
array = [True for i in range(n+1)]

for i in range(2, int(math.sqrt(n))+1):
  if array[i] == True: #거치지 않은 수
    j = 2
    while i*j <= n:
      array[i*j] = False # 
      j += 1

#출력
for i in range(2, n+1):
  if array[i] == True :
    print(i, end = ' ')

우선 소수를 판별하는 리스트를 n만큼 True로 선언해준다. 우선, 다 소수라고 명시해주는 것이다.

2부터 루트n만큼 반복문을 도는데, j를 2부터 1씩 증가해가며 i와 곱해주고, 그 값에 해당하는 값을 false로 바꿔준다.

즉, 2~1000까지에서 2의 배수를 지워준다음, 3의 배수 ~~~ 루트 n의 배수까지 모두 지워준다.

그것이 소수이다.