[Algorithm] 에라토스테네스의 체

에라토스테네스의 체

 

1. 알고리즘의 이해

1. 2부터 n까지 반복문을 돌린다
2. 아직 체크가 되지 않은 수를 방문한다
3. 아직 체크가 되지 않았다는 것은 이 수는 소수라는 뜻이다
4. 이 수의 모든 배수는 소수가 아니므로 반복문을 돌며 체크해준다

 

 

2. 소스 코드

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int prime[1000001];

bool eratos(int n){
    memset(prime, true, sizeof(prime));
    
    for(int i=2; i<=n; i++){
        if(prime[i]){
            for(int j=i+i; j<=n; j+=i){
                prime[j] = false;
            }
        }
    }
    
    if(prime[n])
        return true;
    else
        return false;
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    int n;
    cin >> n;
    
    if(eratos(n)){
        cout << 1 << "\n";
    }else{
        cout << 0 << "\n";
    }
    
    return 0;
}

 

 

3. 추가 문제

k번째로 지워진 소수를 찾아라!!

문제 링크 : https://www.acmicpc.net/problem/2960

#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;

int n,k,cnt,ans;
bool flag;
bool prime[1001];

void eratos(){
    memset(prime, true, sizeof(prime));
    cnt = 0;
    flag = true;
    
    for(int i=2; i<=n; i++){
        if(prime[i]){
            prime[i] = false;
            cnt++;
            
            if(cnt == k){
                ans = i;
                break;
            }
            
            for(int j=i+i; j<=n; j+=i){
                if(prime[j]){
                    prime[j] = false;
                    cnt++;
                    
                    if(cnt == k){
                        ans = j;
                        flag = false;
                        break;
                    }
                }
            }
            
            if(!flag) break;
        }
    }
    
    cout << ans << "\n";
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n >> k;
    
    eratos();
    
    return 0;
}