소수를 빠르게 구하는 에라토스테네스의 체 알고리즘

1. 소수를 구하는 방법

 

컴퓨터가 주어진 수 n이 소수인지 판단할려면 어떻게 해야할까? 

 

1부터 n까지 n에 나눠보면서 n의 약수인지 아닌지 판단해보면 된다.

 

n의 약수가 1과 n만 있어야 n이 소수이다.

 

#숫자 n이 소수이면 True, 아니면 False

#단 1은 소수가 아니다

def is_prime(n):
    
    if n == 1:
        
        return False
    
    else:
        
        for i in range(2,n): #1과 n으로는 당연히 나누어 떨어지니까, 2~n-1까지 검사
            
            if n % i == 0:
                
                return False
        
        return True

 

2. 에라토스테네스의 체

 

2-1) 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다.

 

2-2) 2를 제외한 2의 배수를 모두 지운다

 

2-3) 3을 제외한 3의 배수를 모두 지운다

 

2-4) 5를 제외한 5의 배수를 모두 지운다

 

2-5) 7을 제외한 7의 배수를 모두 지운다

 

....

 

2-6) 계속 반복한다

 

2-7) 구간에 모든 소수가 남는다

 

>>> "주어진 수 i가 소수라면, i를 제외한 모든 i의 배수를 False로 바꿔준다"

 

def get_prime(n): #n까지 숫자 중에서 소수를 구하는 방법
    
    steve = [True] * (n+1) #0~n까지가 모두 소수라고 표시한 초기화된 형태
    
    for i in range(2,n): #2부터 n-1까지를 검사
        
        if steve[i]: #i번째 수가 소수라면,
        
        #step size가 i라면 i의 배수씩 검사하게 되는거
            
            for j in range(i+1,n+1,i): #i를 제외한 i의 배수를 모두 제거
                
                steve[j] = False
    
    return [i for i in range(2,n+1) if steve[i] == True] #2부터 n까지 True인 수를 모두 리스트에 담아 return

 

3. 최적화하기

 

사실 2부터 n까지 검사할 필요 없이 n의 제곱근까지만 검사해도 된다는 사실은 이미 공부한 사실이다

 

정수 n = a*b로 나타낼 수 있을 때 a가 커지면, b가 자연스럽게 감소할 것이다.

 

그리고 a가 결정되면, n을 a로 나누면 b가 자연스럽게 결정된다.

 

그러니까 a를 안다면 b는 사실 아는거나 마찬가지다.

 

그래서 n이 a로 나누어 떨어진다면, b를 굳이 안구해봐도 a에 대응하는 b로 나누어 떨어지는건 당연하다

 

그렇다면 a는 최대 어디까지 증가할 수 있을까?

 

$n = \sqrt{n} * \sqrt{n}$이므로 a의 최댓값은 $\sqrt{n}$까지이다.

 

따라서 2부터 $\sqrt{n}$까지 n에 나눠보고 나누어 떨어지는 수가 존재하지 않으면 n은 소수이다.

 

def get_prime(n):
    
    steve = [True] * (n+1)
    
    for i in range(2,int((n+1)**(1/2))+1): #제곱근값까지 검사를 해야함 그래서 +1해줘야
        
        if steve[i]:
            
            for j in range(i+1,n+1,i):
                
                steve[j] = False
    
    return [i for i in range(2,n+1) if steve[i] == True]

 

 

4. 연습문제

 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWRuoqCKkE0DFAXt&categoryId=AWRuoqCKkE0DFAXt&categoryType=CODE&problemTitle=%ED%85%8C%EB%84%A4%EC%8A%A4&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

SW Expert Academy

 

D가 주어질 때, A이상 B이하의 수 중에서 D를 포함하는 소수의 개수를 구하는 문제

 

A,B의 최대범위가 1000000이므로, 여기까지 에라토스테네스의 체를 이용해서 모든 소수를 구해놓은 다음에

 

테스트케이스에서 제시한대로 A이상 B이하의 수를 걸러내고, 그 중에서 D를 포함하는 소수의 개수를 센다

 

#주어진 최대구간에서 모든 소수를 미리 찾아놓는다
def get_prime(n):
    
    arr = [True]*(n+1)
    
    for i in range(2,int((n+1)**(1/2))+1):
        
        if arr[i]:
            
            for j in range(i+i,n+1,i):
                
                arr[j] = False
    
    return [i for i in range(2,n+1) if arr[i] == True]

max_prime_set = get_prime(1000000)

T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for t in range(1, T + 1):
    # ///////////////////////////////////////////////////////////////////////////////////
    
    d,a,b = map(int,input().split())
        
    ans = 0
    
    #구해놓은 모든 소수 리스트에서
    
    for p in max_prime_set:
    
    #a이상 b이하의 소수를 찾고
        
        if p >= a and p <= b:
        
        #그 소수 p에서 d를 포함하고 있다면
              
            if str(d) in str(p):
            
            # 그 소수의 개수를 count한다
                
                ans += 1
        
        #만약 소수 p가 b보다 크다면, 더 검사할 필요도 없으므로 바로 break
        elif p > b:
              
            break
                    
                    
    
    print('#'+str(t),ans,sep=' ')
            
            
   
    # ///////////////////////////////////////////////////////////////////////////////////

a이상 b이하의 수를 어떻게 찾냐??

 

뭐 이상한 잔기술 필요도 없이 아주 정직하게 if문 이용해서 a이상 b이하인지 검사하면 그만임

 

언제든 기본이 제일 중요하다는거

 

ans = 0

for p in max_prime_set:

#a이상 b이하의 소수를 찾고

    if p >= a and p <= b:

    #그 소수 p에서 d를 포함하고 있다면

        if str(d) in str(p):

        # 그 소수의 개수를 count한다

            ans += 1

    #만약 소수 p가 b보다 크다면, 더 검사할 필요도 없으므로 바로 break
    elif p > b:

        break