[백준] 4948_베르트랑 공준

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

4948번: 베르트랑 공준

 

이 문제는 소수를 일일이 구한다면 제한된 시간내에 어렵다고 보면 된다.

 

 

그래서 

'에라토스테네스의 체' 알고리즘이란,
2부터 소수를 구하고자 구간의 모든 수에서

2 * 2 , 2 * 3, 2 * 4 ,,,,
2부터 2곱한 수, 3곱한수를 지운다.
3도 마찬가지로, 3 * 2, 3 * 3, 3 * 4,,,


일정 구간까지 곱한 수의 배수를 지운다. 

위 과정을 반복한다면 소수가 남는다.

 

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

 

 

 

1. 수를 받는다
2. 2부터 그 수의 제곱근까지
   • 2부터 ~ 배수가 <= 2 * 그 수까지  (문제에서 2N수까지 소수를 구하라고 해서
   • 배열[그 수의 배수] 자리에 -1를 넣는다.
3. 받은 수부터 2N까지 -1이 아닌 수가 나오면 sum++

 

 

 

※ 이게 배열에 -1넣는 것의 중복을 피하기 위해,

이전 값이 어디까지 곱했는지 기억하고, 그 안의 수를 알고 싶을 땐 안 한 값만 하고싶었는데

틀렸다,, 근데 구현을 한다면 할 수 있을 것 같다.

 

 

소스코드↓

#include<stdio.h>
#include<math.h>



int main() {
	int num;
	
	int sum = 0;
	int check[246913] = { -1,-1,1 };
	
		
	while (1) {

		scanf("%d", &num);
		if (num == 0)
			return 0;
		
		for (int end_num = 2; end_num <= sqrt(2 * num); end_num++) {
			for (int j = 2; end_num * j <= 2 * num; j++) {
				check[end_num * j] =-1;
 			}
		}
		sum = 0;
		for (int i = num+1; i <= 2 * num; i++) {
			if (check[i] >-1)
				sum++;
		}
		printf("%d\n", sum);
		if(befor_num < num * 2)
			befor_num = num * 2;
	}

}