에라토스테네스의 체 ( Sieve of Eratosthenes ) - C++

오... 이건 또 무엇인가. 백준 17425번을 풀다가 접한 이론이다.

소수를 찾는 방법중 하나이다. 이 방법은 마치 체로 치듯이 수를 걸러낸다고 하여 '에라토스테네스의 체'라고 불린다.

# 방법 #

임의의 자연수 N 에 대해 그 이하의 소수를 찾는 가장 간단하고 빠른 방법이다.   예를 들어 1 ~ 100 까지 숫자 중 소수를 찾는다고 하자.

( The sieve of Eratosthenes is one of the most efficient ways to find all primes smaller than N when N is smaller than 10 million or so. ) 

1. 우선 1 ~ 100 까지의 수가 있다.

( Let us take an example when N = 100. So, we need to print all prime numbers smaller than or equal to 100 )

2. 먼저 소수도, 합성수도 아닌 유일한 자연수 1을 제거한다.

( We create a list of all numbers from 2 to 100 ).

3. 2를 제외한 2의 배수를 제거한다.

( According to the algorithm we will mark all the numbers which are divisible(나눌수 있는) by 2 and are greater than or equal to the square of it. ) 

3. 3을 제외한 3의 배수를 제거한다.

( Now we move to our next unmarked number 3 and mark all the numbers which are multiples of 3 and are greater than or equal to the square of it . )

4. 4의 배수는 제거할 필요 없다. (2의 배수에서 이미 지워짐.) 그리고, 2,3 다음으로 남아있는 소수인 5, 즉 5를 제외한 5의 배수를 제거한다.

( We move to our next unmarked number 5 and mark all multiples of 5 and are greater than or equal to the square of it. )

5. 그리고 마지막으로 7을 제외한 7의 배수까지 제거한다. 8의 배수도, 9의 배수도 제거할 필요 없다. 10의 배수도 필요없음 ! 그리고 11이상부터의 소수들의 배수 부터는 11 > 루트100 (10)  이기 때문에 , 역시 지울 필요 없다.

( We continue this process and our final table will look like below: )

( So, the prime numbers are the unmakred ones : 2,3,5......)

위의 제거 과정을 거친 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97이 남는다. 이것이 100 이하의 소수이다.

이런 방법으로, 만약 N 이하의 소수를 모두 찾고 싶다면, 1 ~ N 까지 쭉 나열한 다음에, 2,3,5의 배수를 쭉쭉 나누는 것이다. 

다만, 이 방법은, ' 특정 범위 내의 소수' 를 판정하는 데에만 효율적이다.

만약 주어진 수 하나가 소수인가? 를 따지는 상황이라면, 이는 소수판정법이라 해서 더 빠른 방법이 있다. 

 

# Sieve of Eratosthenes in O(n*log(log(n))) time complexity , Auxiliary Space: O(n)

// C++ program to print all primes smaller than or equal to
// N using Sieve of Eratosthenes
 
#include <iostream>
using namespace std;
 
void SieveOfEra(int n) {
 
    // Create a boolean array "prime[0 .. n]" and initialize
    // all entries it as true. A value in prime[i] will 
    // finally be false if i is Not a prime, else true. 
    // 먼저 다 1로 설정하고, i가 소수가 아니면 false가 될거임. 소수면 true.
 
    bool prime[n+1];
    memset(prime, true, sizeof(prime));
 
    // p*p 인 이유는, 시작하는 수(예를들어 2면 4부터)의 배수 부터 지워야하기 떄문. 
    for(int p = 2; p*p <= n; p++) { 
        if(prime[p] == true) {
            for(int i = p*p; i <= n; i += p ) 
                // 예를들어 p가 2면, 2씩 숫자가 늘어나야 하니까.. i += p 를 해줌.
                prime[i] = false; // 배수(p^2)들을 전부 false 처리 해준다. 
        }
    }
 
    // Print all prime numbers
    for( int p = 2; p <= n; p++)
        if(prime[p]) cout << p << " ";
    cout << '\n';
 
}
 
int main()
{
    int n = 30;
    cout << "Following are the prime numbers smaller than or equal to : " << n << '\n';
    SieveOfEra(n);
    return 0;
}

 

# O(n) time complexity. ..... (어렵당)

2개의 예시가 있는데........ 

// The following implementation
// stores only halves of odd numbers
// the algorithm is a faster by some constant factors.
 
#include <iostream>
#include <bitset>
using namespace std;
 
bitset<500001> Primes;
 
void SieveOfEra(int n) {
 
    Primes[0] = 1;
    for(int i = 3; i*i <= n; i+2 ) {
        if(Primes[i/2] == 0) {
            for(int j = 3*i; j <= n; j += 2 * i)
                Primes[j/2] = 1;            
        }
    }
}
 
int main()
{
    int n = 100; 
    SieveOfEra(n);
 
    for( int i = 1; i <= n; i++) {
        if ( i == 2 ) cout << i << ' ';
        else if ( i%2 == 1 && Primes[i/2] == 0) {
            cout << "what num?! : " << i << '\n';
        }
    }
    return 0;
}
 
 
 

뭐 여기까지만 알아도 될듯 ^^.... ㅎㅅㅎ;

 

++ 

https://www.acmicpc.net/problem/17425

17425번: 약수의 합

그래서 여기서 풀어보는 약수의 합 골드 !  주석을 참고하자. 

#include <iostream>
using namespace std;
long long dp[1000001];
 
int main() {
    int n, t;
    cin >> n;
    
    // 여기서 모든 경우의 수 다 구하고, 
    for(int i = 1; i <= 1000001; i++) {
        for(int j = i; j <= 1000001; j+=i) {
            dp[j] += i;
        }
    }
    // dp 로 이전 케이스 더하는 식으로 해서 모든 테스트 케이스의 결과값을 구해놓는다.
    for(int i = 2; i <= 1000001; i++) {
        dp[i] += dp[i-1];
    }
 
    // 그리고 위에서 구해놓은 값으로 입력받은 테스트 케이스의 결과값 바로바로 출력한다. 
    for(int j = 0; j < n; j++) {
        scanf("%d", &t);
        printf("%lld\n", dp[t]);
    }
    
    return 0;
}