소수

시작하기 앞서 ...

수많은 발견과 증명이 존재하는 수학의 세계에서 소수는 아직도 미지의 분야이다. 오늘은 소수를 감춘 베일을 조금이나마 옅보고자 한다.

소수의 정의

소수: 1과 그 수 자신으로만 똑 떨어지게 나눌 수 있는 정수

예) 2, 3, 5, 7, 11 등

소수를 찾는 알고리즘 만들기

Step 1) 소수를 찾기 위해 어떠한 수가 다른 수로 나뉘어지는지 확인하기

# N이 d로 나누어 지는지 확인하기

n, d = map(int, input().split())

if n % d == 0:
  print(True)
else:
  print(False)

Step 2) 이를 활용한 약수 구하기

# N의 약수 구하기

n = int(input())
factors = []

for i in range(1, int(n**(1/2))+1):
  if n % i == 0:
    factors.append(i)
    if n != i ** 2:
      factors.append(n//i)

factors.sort()
print(factors)

Step 3) 이를 개선한 소수 구하기

# N이 소수인지 확인하기
# 1과 N은 당연히 나눠지므로 2부터 N까지 해야한다

n = int(input())
isPrime = True

for i in range(2, n):
  #int(n**(1/2))
  if n % i == 0:
    isPrime = False
    print(isPrime)
    break

Step 4) 위 코드와 함수를 접목시켜 소수 구하기

# 함수 이용하기
# return이 있어 훨씰 편하다


def isPrime(n):
  
  isPrime = True

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

isPrime(27) # 안의 숫자는 입력받은 값이나 값을 가지는 변수를 넣어도 된다.

Step 5) 응용: N보다 작은 소수 모두 찾기

# N보다 작은 소수 모두 찾기
# 반복문을 돌며 위 함수를 적용시키면 된다.

n = int(input())

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

for i in range(2, n-1):
  if isPrime(i):
    print(i)

Step 6) 새로운 알고리즘: 에라토스테네스의 체

에라토스테네스의 체 설명

에라토스테네스의 체:

1. 수를 1부터 원하는 수까지 나열하여
2. 소수도, 합성수도 아닌 유일한 자연수 1을 제거하고
3. 2 제외 2의 배수를 모두 지운다.
4. 3 제외 3의 배수를 모두 지운다.
5. 4는 이미 지워졌다.
6. 5 제외 2의 배수를 모두 지운다.
7. 6은 이미 지워졌다.
8. 7 제외 2의 배수를 모두 지운다.
9. 위의 방법을 반복하면 지워지지 않은 수는 소수이다.

이렇게 하면 2를 지우면 2^n도 모두 지워지니 계산이 배는 빨라진다. 에라토스테네스의 체는 매우 효율적으로 소수를 찾는 알고리즘이다.

에라토스테네스의 체 알고리즘화

빈 리스트를 만들어 숫자의 인덱스와 숫자가 같다고 가정한다.
소수로 판명되면 True이고 아니면 False로 바꾼다.
마지막에 True인 친구들의 인덱스만 뽑아낸다.

따라서

1. N+1 개의 True가 담긴 리스트를 만든다
2. 0과 1은 Flase로 만든다.
3. 리스트를 처음부터 끝까지 반복하는데,
   그 다음부터 True인 수를 만나면 그 수 외 배수들을 전부 False로 바꾼다.

에라토스테네스의 체 코딩

# 함수를 활용한 에라토스테네스의 체 코드

def primeList(n):
  sieve = [True] * (n+1)
  for i in range(2, int(n**(1/2))+1):
    if sieve[i] == True:
      for j in range(i*2, n+1, i):
        sieve[j] = False
  primeNumber = []
  for a in range(2, n+1):
    if sieve[a] == True:
      primeNumber.append(a)
  return primeNumber

print(primeList(97))

오늘은 소수, 소수를 다루는 여러 코드와 가장 효율적인 알고리즘, 에라토스테네스의 체를 배워보았다. 위의 코드와 설명이 도움이 되었길 바라며 다음 주제를 기대하겠다.