[알고리즘] 에라토스테네스의 체.

에라토스테네스의 체 란?

• 소수를 판별하는 알고리즘이다.
• 소수들을 대량으로 빠르고 정확하게 구하는 방법이다.

단일 숫자 소수 여부 확인

어떤 수의 소수의 여부를 확인 할 때는, 특정한 숫자의 제곱근 까지만 약수의 여부를 검증하면 O(N^1/2)의 시간 복잡도로 빠르게 구할 수 있다.

수가 수(N이라고 가정)를 나누면 몫이 생기는데, 몫과 나누는 수 둘 중 하나는 N 제곱근 이하이기 때문이다.

만약, 대량의 소수를 한꺼번에 판별해야할 경우는 '에라토스테네스의 체'를 이용한다.

소수 구하기

n=100

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

for i in range(n+1):
  if(isPrime(i)):
    print(i)

but 범위가 넓을 시 모든 범위를 훑기에 소요가 많음. -> 소수의 배수들을 배제하는 방법으로 남는 소수를 가져갈 수 있지 않을까?

에라토스테네스의 체 원리

에라토스테네스의 체는 가장 먼저 소수를 판별할 범위만큼 배열을 할당하여, 해당하는 값을 넣어주고, 이후에 하나씩 지워나가는 방법을 이용한다.

1. 배열을 생성하여 초기화한다.
2. 2부터 시작해서 특정 수의 배수에 해당하는 수를 모두 지운다.(지울 때 자기자신은 지우지 않고, 이미 지워진 수는 건너뛴다.)
3. 2부터 시작하여 남아있는 수를 모두 출력한다.

n=1000
a = [False,False] + [True]*(n-1)
primes=[]

for i in range(2,n+1):
  if a[i]:
    primes.append(i)
    for j in range(2*i, n+1, i):
        a[j] = False
print(primes)

def eratos_filter(n):
    sieve = [True]*(n+1)
    # n의 약수는 sqrt(n)이하로 존재할수밖에 없다. 때문에 
    m = int(n**0.5)
    for i in range(2,m+1):
        if sieve[i] ==True:
            # range를 이용 i의 배수들을 걸러줫음.
            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]

n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(n)까지 검사" 이해하기

용어

자연수는 1과 소수와 합성수로 이루어 진다.

소수 : 1과 자기 자신 만을 약수로 갖는 1보다 큰 양의 정수

합성수 : 1과 자기 자신 이외의 약수를 가진 양의 정수

n>m=ab

a,b는자연수,m은합성수

a,b가가능한경우의수를살펴보자

√n,√n−l,√n+s세항모두적절한수l,s이존재해서자연수이다

b가√n이하일때⋯(√n+s)(√n−l)=m1

√n일때⋯√n(√n−l)=m2

∵이경우에는√n=자연수

√n보다클때⋯(√n+s)(√n−l)=m3

첫번째로√n이하일때먼저√n−l에자연수(√n+s)를곱해가면서합성수m1을만들고m1을거른다.⋯ⓐ

√n+s=2,3,4,⋯

두번째로√n일때√n에자연수(√n−l)을곱해가면서합성수m2을만들고m2을거른다.

그런데m2는(√n−l)항때문에ⓐ과정에서이미걸러진수들이다.m2=m1

세번째로√n보다클때역시(√n−l)항때문에이미걸러진수들이다.m3=m2

∴√n이하일때만고려하면된다

즉 소수는 어차피 약수가 지랑 1밖에없으니 고려 안해도 되고

합성수의 약수도 반드시 제곱근 이하일수밖에 없으니 int로 바꿔서 내려가는 값만 +1 더해주고 그 아래값들만 조사한다.