백준 #1929 소수 구하기 (c++)

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

1929번: 소수 구하기

자자 소수 구하는 문제가 나왔으면 뭐다?

바로 "에라토스테네스의 체"를 떠올려야 한다는 것이다

 

에라토스테네스의 체란, 이 문제에 적용해봤을 때

M부터 N까지의 자연수 중 2부터 N(최댓값)의 제곱근값까지의 자연수로 나누어봤을때 자신과 다른 값의 자연수들 중에 그 어떤 값과도 나누어떨어지지 않았을 경우 그 자연수는 소수라는걸 결정해주는 이론이다.

 

나 또한 그 이론을 사용해서 코드를 짜봤는데 틀렸습니다가 여러번 나오는 바람에 대체 뭐가 문제인건지 한참을 헤맸다.

그러던 와중 정말 당연하지만 까먹고 있었던 정말 중요한 사실을 잊고 있었다.

 

그것은 바로..

 

1은 소수가 아니라는 점이다 (게다가 합성수도 아니라고 하네요)

 

이 사실을 망각한채 코드에서 M과 N사이의 자연수 중 1이 있는 경우에(M이 1인 경우)는 출력하지 않아야한다는 조건을 안 추가해줬다.

그래서 바로 코드를 추가해줬더니 역시나.. 바로 맞았습니다가 떠버렸다.

#include <iostream>
#include <cmath>
#define FASTIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
using namespace std;

int M, N;

int main() {
	FASTIO;
	cin >> M >> N;
	int upto = floor(sqrt(N));
	for (int i = M; i <= N; i++) {
		if (upto == 1 && i != 1) {
			cout << i << '\n';
		}
		for (int j = 2; j <= upto; j++) {
			if (i % j == 0 && i != j) break;
			else if (i != 1 && j == upto) cout << i << '\n';
		}
	}
}

---

*** 오늘의 잊지 말아야할 point ***

1은 소수도, 합성수도 아니다 !!

 

다음부턴 잊지 말고 꼭 1일 때에도 고려해보자