(C++) ★Number Theory Intermediate I - 2 Solved★

★ 1929 소수 구하기 ★

//1929
#include <iostream>
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#include <set>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int M, N;
    cin >> M >> N;
    vector <int>sieve(N+1, true);

    for(int i=2;i<=(int)sqrt(N);i++){
        if(sieve[i] == true){
            int j = 2;
            while(i*j<=N){
                sieve[i*j] = false;
                j+=1;
            }
        }
    }

    for(int i=M;i<=N;i++){
        if (sieve[i] && i!=1){
            cout << i << '\n';
        }
    }

	return 0;
}

👳🏻‍♀️ vector<int> sieve 가변 배열을 만든다. (N+1, true)를 뒤에 붙이면 총 N+1개의 자리가 있고 모두 true로 initialization.

 

👳🏻‍♀️자연수 N까지의 모든 소수 구하기 (에라토스테네스의 체)

(1) 2부터 root(N)까지 돌리기

(2) 돌리며 해당 값 sieve[i]가 true일 때, i를 2배 이상 곱한 결과부터 N까지의 모든 i의 배수를 false 처리(배수이므로 소수 x)

(3) 최종적으로 true인 것만 소수(단 0과 1 제외)

---

★ 4948 베르르랑 공준 ★

//4948
#include <iostream>
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#include <set>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, ans;

    while(true){
        cin >> n;
        ans = 0;
        if(n==0){
            break;
        }
        vector<int> sieve(2*n+1,true);
        sieve[0] = false;
        sieve[1] = false;

        //sieve of eratosthenes
        for(int x=2;x<=(int)sqrt(2*n);x++){
            if(sieve[x]){
                int j = 2;
                while(x*j<=2*n){
                    sieve[x*j] = false;
                    j += 1;
                }
            }
        }

        for(int i=n+1;i<=2*n;i++){
            if(sieve[i]){
                ans+=1;
            }
        }
        cout << ans << endl;
    }

	return 0;
}

 

👳🏻‍♀️ 2*n+1(0 포함)개의 숫자가 들어갈 수 있는 sieve 완성해서 n+1부터 2*n까지의 소수의 개수 구하기

---