에라토스테네스의 체

Silver3 1929

첫시도

using namespace std;


int main() {

	
	int a, b;
	int cnt;
	scanf("%d %d", &a, &b);
	for (int i=a; i <= b; i++) {
		cnt = 0;
		for (int j = 2; j <= i; j++) {
			if (i % j == 0) {
				cnt++;
			}
		}
		if (cnt == 1) {
			printf("%d\n", i);
		}
	}
	return 0;
}

시간복잡도가 초과가 되었다
이 문제는 에라토스테네스의 체 알고리즘을 이용하여 풀어야 하는 문제이다.

시간 제한 : 1초에 1억번 연산과 비슷
시간제한 2초니까 2억번 연산안에 답이 도출 되어야 한다.
2중 for문은 N^2만큼 연산이 된다
N이 최대로 들어올수있는 1,000,000이 들어오면
1,000,000,000,000(약 1조번)연산을 하므로 시간초과가 뜬다

두번째 시도

using namespace std;


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


	int a,b;
	cin >> a>>b;
	bool* PrimeArray = new bool[b + 1];
	for (int i = a; i <= b; i++) {
		PrimeArray[i] = true;
	}
	for (int i = 2; i <= b; i++) {
		if (PrimeArray[i] == false) continue;
		for (int j = i + i; j <= b; j = j + i) {
			PrimeArray[j] = false;
		}
	}

	for (int i = a; i <= b; i++) {
		if (PrimeArray[i]) {
			cout << i << '\n';
		}
	}

	return 0;
}

에라토스테네스의 체 알고리즘을 이용하여 풀었지만 출력초과가 나왔다.
첫번째 for문에서 a=2일 경우를 true로 초기화하지 않아 반례가 발생하였다.

#include <iostream>
using namespace std;


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


	int a, b;
	cin >> a >> b;
	bool* PrimeArray = new bool[b + 1];
	for (int i = 2; i <= b; i++) {
		PrimeArray[i] = true;
	}
	for (int i = 2; i <= b; i++) {
		if (PrimeArray[i] == false) continue;
		for (int j = i + i; j <= b; j = j + i) {
			PrimeArray[j] = false;
		}
	}

	for (int i = a; i <= b; i++) {
		if (PrimeArray[i]) {
			cout << i << '\n';
		}
	}

	return 0;
}

---

Silver 2581

첫시도

#include <iostream>
using namespace std;

bool PrimeArray[10001];
int main() {
	int M, N,sum=0,min=10000;
	cin >> M >> N;
	for (int i = 2; i <= N; i++) {
		if (PrimeArray[i] == true)continue;
		for (int j = i + i; j <= N; j = j + i) {
			PrimeArray[j] = true;
		}
	}
	for (int i = M; i <= N; i++) {
		if (PrimeArray[i]==false) {
			sum = sum + i;
			if (i < min) { min = i; }
		}
	}
	if (sum == 0) { cout << -1; return 0; }
	cout << sum << '\n';
	cout << min << '\n';

	return 0;
}

예제 입력은 다 맞게 나오는데 틀렸습니다가 나왔다.

두번째시도

#include <iostream>
using namespace std;

bool PrimeArray[10001];
int main() {
	int M, N,sum=0,min=10000;
	cin >> M >> N;
	PrimeArray[1] = true;
	for (int i = 2; i <= N; i++) {
		if (PrimeArray[i] == true)continue;
		for (int j = i + i; j <= N; j = j + i) {
			PrimeArray[j] = true;
		}
	}
	for (int i = M; i <= N; i++) {
		if (PrimeArray[i]==false) {
			sum = sum + i;
			if (i < min) { min = i; }
		}
	}
	if (sum == 0) { cout << -1; return 0; }
	cout << sum << '\n';
	cout << min << '\n';

	return 0;
}

반례가 M, N이 모두 1일 때 발생한다
1은 소수가 아니기 때문에 시작할 때 PrimeArray[1] = true;로 초기화 하면 정답이다.

• 깨달은 점 : 항상 답안지 제출 전에 최솟값, 최댓값 대입해보고 성립 하는지 확인 해야한다 은근히 여기서 많이 틀림!