Algo 01 - 반복문, 에라토스테네스의 체

반복문

반복문 에는 while, for문이 있는데

이번에는 그 중에서 가장 많이 사용하는 for문 에서

알고리즘 시작 할 때 대표급으로 많이 보는

에라토스테네스의 체 를 설명 하려고 한다.

에라토스테네스의 체

난이도 별 1개?

에라토스테네스의 체 소수를 구하는 알고리즘 이다.

소수를 어떻게 컴퓨터가 빠르게 계산하도록 할까? 에 대한 고민에서 나온 알고리즘 이다.

소수의 정의는 1과 자신 외에는 나누어 지지 않는 수를 뜻하며 이는 수학적으로 컴퓨터 과학 적으로 매우 중요한 수인데

소수가 커질 수록 구하는 방법이 여간 쉽지는 않다.

그렇다면 이 알고리즘은 어떤 아이디어 일까?

내가 원하는 범위에서 같은 행동을 반복적으로 해서 소수를 찾는 방법인데

• 이 방법도 너무 큰 수는 이방법으로 구할 수없다.

룰은 간단하다.

1. 2번 부터 시작하는데 자기 자신 부터 구하려는 범위 까지 자기의 배수들은 소수가 아니라고 표시한다.
2. n 번째 수에 도달 했을 때, 앞에 수의 배수를 제외하는 행동에서 제외 되지 않았다면 소수이다, 제외 됬다면 이수는 소수가 아니다.
3. 자기 자신에 도착 했을 때 제외되는 수가 아니라면 자기의 배수들을 제외한다.

이를 간단히 표시하자면 아래의 행동이다.

출처 : https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

2 는 제외 된 적이 없으니 소수이고 2의 배수들을 모두 제외한다.
3 도 2와 같다.
4는 이미 제외 되었기 때문에 넘어간다.
5는 제외되지 않아서 5의 배수들은 제외한다.
2,3,5 는 소수이다.

문제 풀이

문제 : acmicpc.net/problem/2960

code

#include<iostream>

using namespace std;

int N = 1000, k, cnt; // 값 미지정 int 는 0

bool isPrime[1001]; // 초기 값은 false
//제외된 수는 true 값으로 표기

int main(){
    scanf("%d %d", &N, &k);
    
    for(int i=2; i<=N; i++){ // 2부터 점진적으로 숫자를 나아간다.

        if(!isPrime[i]){ // 제외 되지 않았다면 (=false) 
            for(int j=i; j<=N; j+=i){ // 제외 되지 않은 수 (i)에 대해서 배수들을 제외한다.
                if(isPrime[j]==false){
                    isPrime[j]=true; //true 값을 주어 제외한다.
                    if(++cnt==k){
                        // 제외 하는 순서중 k번째인 수 
                        printf("%d\n", j);
                        return 0;
                    }
                }
            }
        }
    }
    return 0;
}

알고리즘적 생각 정리

전제 조건 : 특정 구간에 대한 모든 소수를 찾으려고 할 때

단순 구현 : 모든 숫자 n에 대해서 2~n-1인 수를 모두 나눠보고 나눠지지 않으면 소수

중복 행동 : n번째 수에 대해서 x로 나눠서 안나눠 진다고 판별 되면 x의 배수로 나누는 행동은 무의미하다. 17이 2로 안나눠 진다면 2의 배수인 4, 8, 16 으로는 당연히 나눠어 지지 않는다.

알고리즘 행동 : 중복 행동에서 정의한 행위는 너무 비효율 적, 특정 숫자 n이 소수인지 판별하는 행위는 n이전의 소수들에 대해서만 나누어 지는지 확인하면 된다.

n이라는 수가 모든 수로 나누어지는지 확인 하지 말고 n이전의 소수들에 대해서 나누어 지는지만 확인하자

다른 for문 연습 문제들

간단하게 for문에 대하여 정리할결 풀기 좋은 건

별 찍기 인 것 같다.

다만 여러가지 시도하면서 하지 말고 각각의 for문의 해야 할 일에 대해서 생각 하면서 짜는 걸 추천한다. 위의 코드의 for문 옆에 있는 주석 처럼

https://www.acmicpc.net/problem/2438
https://www.acmicpc.net/problem/2439
https://www.acmicpc.net/problem/2440

위의 문제들을 추천합니다.