백준 4948_베르트랑 공준

 

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

4948번: 베르트랑 공준

 

- 에라토스테네스의 체 알고리즘

 

 

 

1. N+1크기의 배열을 선언한다.
2. 배열을 모든 요소를 0으로 초기화한다.
3. 배열의 인덱스가 2의 배수인 모든 칸을 1로 초기화한다.
4. 그 다음수인 3을 선택한다.
5. 배열의 인덱스가 3의 배수인 모든 칸을 1로 초기화한다.
6. 그 다음 소수인 5를 선택한다.
7. 배열의 인덱스가 5의 배수인 모든 칸을 1로 초기화한다.
8. 위 내용을 N까지 반복한다.

 

void func(int n)
{
	int arr[n+1]={0,};
        int i,j;
        for(i=2; i<=n; i++){
                if(arr[i]==1){
                        continue;
                }
                for(j=2*i; j<=n; j+=i){
                        arr[j]=1;
                }
        }
}

 

---

 

- 베르트랑 공준 문제 풀이

 

#include <stdio.h>
int arr[246913]; //전역변수는 초기화 하지 않으면 0으로 자동초기화됨
void func(int n)  //소수 구하기
{
        int i,j;
        for(i=2; i<=2*n; i++){
                if(arr[i]==1){
                        continue;
                }
                for(j=2*i; j<=2*n; j+=i){
                        arr[j]=1;
                }
        }
}
int main()
{
        int n;
        int i,sum=0;
        func(123456); //문제에서 범위가 (N <= 123456)
        while(1){
                scanf("%d", &n);
                if(n==0)
                        return 0;
                sum = n;
                for(i=n+1; i<=2*n; i++)
                        sum-=arr[i];
                printf("%d\n", sum);
        }
}