[이것이 코딩 테스트다 with Python]_38_에라토스테네스의 체

220216 작성

<본 블로그는 『이것이 취업을 위한 코딩 테스트다』 의 youtube를 참고해서 공부하며 작성하였습니다>

https://www.youtube.com/watch?v=9rLFFKmKzno&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=38 

 

 

 

 

 

 

 

1. 다수의 소수 판별

: 특정한 수의 범위 안에 존재하는 모든 소수 찾을 때는 어떻게??

 

 

 

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

: 다수의 자연수에 대하여 소수 여부를 판별할 때 사용

: N보다 작거나 같은 모든 소수 찾을 수 있음

 

1) 2부터 N까지의 모든 자연수 나열

2) 남은 수 중 아직 처리하지 않은 가장 작은 수 i 찾기

3) 남은 수 중 i의 배수 모두 제거 (i 는 제거 X)

4) 더 이상 반복할 수 없을 때까지 2번, 3번 과정 반복

 

 

 

 

• python

import math

n = 1000 # 2부터 1,000까지의 모든 수에 대하여 소수 판별
array = [True for i in range(n + 1)] # 처음엔 모든 수가 소수(True)인 것으로 초기화

# 에라토스테네스의 체 알고리즘 
for i in range(2, int(math.sqrt(n)) + 1): # 2부터 n의 제곱근까지의 모든 수를 확인하며
    if array[i] == True: # i가 소수인 경우 (남은 수인 경우)
        # i를 제외한 i의 모든 배수를 지우기
        j = 2 
        while i * j <= n:
            array[i * j] = False
            j += 1

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

• c++

#include <bits/stdc++.h>

using namespace std;

int n = 1000; // 2부터 1,000까지의 모든 수에 대하여 소수 판별
// 처음엔 모든 수가 소수(True)인 것으로 초기화(0과 1은 제외)
vector<int> arr(n + 1, true);

int main() {
    // 에라토스테네스의 체 알고리즘 수행
    // 2부터 n의 제곱근까지의 모든 수를 확인하며
    for (int i = 2; i <= (int) sqrt(n); i++) {
        // i가 소수인 경우(남은 수인 경우)
        if (arr[i] == true) {
            // i를 제외한 i의 모든 배수를 지우기
            int j = 2;
            while (i * j <= n) {
                arr[i * j] = false;
                j += 1;
            }
        }
    }
    // 모든 소수 출력
    for (int i = 2; i <= n; i++) {
        if (arr[i]) cout << i << ' ';
    }
}

• java

import java.util.*;

class Main {
    // 소수 판별 함수(2이상의 자연수에 대하여)
    public static boolean isPrimeNumber(int x) {
        // 2부터 (X-1) 까지의 모든 수 확인하며
        for (int i = 2; i < x ; i++) {
            // x가 해당 수로 나누어떨어진다면
            if (x % i == 0) {
                return false; // 소수가 아님
            }
        }
        return true; // 소수임
    }

    public static void main(Strin

 

 

=> 선현 시간에 가까울 정도로 매우 빠르다

=> 시간 복잡도는 O(NloglogN)

=> 각 자연수에 대한 소수 여부 저장해야 돼서 메모리 많이 필요