백준 4948_베르트랑 공준.cpp

<소스코드>

#include <iostream>
#include <cmath>
using namespace std;
int *Eratosthenes(int a, int b){
    int *arr;
    arr = (int *)malloc(sizeof(int) * b);
    for(int i = 2; i <= b; i++){
        arr[i] = i;
    }

    for(int i = 2; i <= sqrt(b); i++){
        if(arr[i] == 0) continue;
        for(int j = i*i; j <= b; j += i){
            arr[j] = 0;
        }
    }
    return arr;
}
int main(){
    int *arr = Eratosthenes(1,246912);
    int n;
    while(1){
        cin >> n;
        int cnt = 0;
        if(n == 0) return 0;
        for(int i = n+1; i <= 2*n; i++){
            if(arr[i] != 0){
                cnt++;
            }
        }
        cout << cnt << endl;
    }


    return 0;
}

1. 변수
   int *Eratosthenes(int a, intb) : a와 b사이의 모든 소수를 찾아주는 함수
   int n : 입력받은 자연수
   int cnt : 소수 개수

2. 알고리즘
   1) Eratosthenes 함수를 이용해서 1 ~ 246912에 모든 소수를 판별한 배열을 리턴받는다.
   2) while문을 돌면서 입력받은 n의 n+1 ~ 2*n까지의 숫자 중 소수이면(arr[i] != 0) cnt의 값을 늘려준다.

3. 배운점
   1) Eratosthenes의 체 :
   소수란 약수가 오로지 1인 수이다. 즉, 1을 제외한 수의 배수가 되는 수는 소수가 아니다.
   임의의 수 n 까지의 소수를 구하고자 할 때

• 2부터 n의 제곱근까지 돌며
  :for(int i = 2; i <= sqrt(b); i++)
• 모든 배수들을 소수에서 제외시키는 방식이다.
  : for(int j = i*i; j <= b; j += i)
  arr[j] = 0;
  ex) if j= 2 -> 4부터 b가 될따까지 4 += 2 이런식으로 제외시킨다.

2) 배열을 리턴하는 함수
int 함수이름{--- return 배열};
int 배열 = 함수;
ex)
int Eratosthenes(int a, int b);
int arr = Eratosthenes(1,246912);

3) 메모리 동적 할당
why? : 프로그램의 실행 중에 입력되는 데이터에 맞게 기억공간을 확보해야 할 때는 동적할당이 필요하기 때문!
메모리를 동적을 할당하기 위해서는 함수를 호출해야 한다
void *malloc(unsigned int);
int arr; //int형을 가리킬 포인트변수
**arr = (int )malloc(sizeof(int));
=> 포인터변수로 각각 할당 받은 기억공간을 참조하여 값을 저장한다.
free(arr) : 동적 할당되는 메모리는 반납해야됨!
=> 메모리를 동적으로 할당 받아 배열로 사용가능!*
**arr = (int )malloc(sizeof(int) * n); **

4) sizeof() : 변수형의 크기

4. 아쉬운점&느낀점
   배운점이 너무 많은 아주 이로운 문제였던거 같다! 적어도 에라토스테네스랑 배열을 리턴하는 함수, 메모리 동적할당은 절대 안 잊어먹어야겠다.