백준 #4948

★☆☆☆☆☆☆☆☆☆

 

---

 

 

 

---

---

---

---

---

문제 접근방식

우선 입력될 숫자의 최댓값이 123456*2이고, 수업 때 배운 에라토스테네스의 체를 이용하여 소수를 미리 선별한다. 그리고, 소수를 저장한 배열에서 (n,2n] 범위에 있는 소수들을 출력하면 되는 문제라고 생각했다.

---

 

vector<bool>subdivide(246913, true); //123456*2까지이므로 미리 사이즈설정
decimal.push_back(1); //소수(decimal)배열에 1을 넣고 시작
	for (int i = 2; i < subdivide.size(); i++) { //2부터 끝까지
		if (subdivide[i]) decimal.push_back(i); //true면 소수

		index = i;
		while (index < subdivide.size()) { //ex)2면 2의 배수들을 다 false처리
			if (!subdivide[index]) { index += i; continue; } //이미 false면 continue
			subdivide[index] = false; 
			index += i;
		}
	}

⑴작은 숫 자부터 시작해서 해당 숫자를 소수 배열에 넣는다.                                                                                                      ⑵그 숫자의 배수들을 모두 소수가 아닌 것으로 처리해준다 이 코드에선 false

*이미 처리된숫자를 만나면 continue 한다

---

정답처리

while (1) {
		int count = 0;
		cin >> num;
		if (num) {
			for (auto& i : decimal) { //소수배열 순회
				if (i > num && i <= (2 * num)) { //주어진 범위설정
					count++; //소수의 개수 카운트
				}
			}
			cout << count << "\n";
		}
		else break; //0이 입력되면 break
	}

소수를 찾고 범위 내에 소수만 개수를 세주면 되므로 쉬운 문제라고 생각한다. 

시간 복잡도:O(n) 에라토스테네스의 체를 구현할 때 가장 많은 연산을 한다.

---

느낀 점 : 이번 주부터는 수학 문제인데 난 수학을 잘 못하기도 했고 까먹은 개념들도 많아서 상당히 시간이 많이 쓰일 것 같다. 그리고 확실히 이제는 시간 복잡도를 어느 정도는 어림짐작하고 문제풀이 방향을 잡는 것 같다 완벽하진 않지만,