C++ 4948 베르트랑 공준

#include <iostream>


using namespace std;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n;
	cin >> n;

	int cnt = 0;
	int res = 0;

	for (int i = n+1; i <= n * 2; i++) {
		for (int j = 1; j <= i; j++) {
			if (i % j == 0)
				cnt++;
		}
		if (cnt == 2)
			res++;
		cnt = 0;
	}
	cout << res << '\n';
	
}

이건 처음에 짠 코드.

결과는 나오지만 답은 아니라고한다.

 

보니까 while을 안넣었다..

#include <iostream>

using namespace std;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	while (1) {
		int n;
		cin >> n;

		int cnt = 0;
		int res = 0;

		for (int i = n + 1; i <= n * 2; i++) {
			for (int j = 1; j <= i; j++) {
				if (i % j == 0)
					cnt++;
			}
			if (cnt == 2)
				res++;
			cnt = 0;
		}
		cout << res << '\n';

	
		if (n == 0)
			break;
	}
}

시간초과..

 

아래는 블로그의 글을 보고 작성한 코드이다.

시간의 차이가 엄청나게 난다.

#include <iostream>
#include <cmath>
using namespace std;

int main() {
	int n, rt, cnt = 0;

	while (1) {
		cin >> n;
		if (!n)	//0 입력시 종료
			break;

		for (int i = n + 1; i <= 2 * n; i++) {
			rt = sqrt(i);
			if (rt == 1 && i != 1) {	//2,3인 경우
				cnt++;
				continue;
			}
			if (i % 2) {	//홀수일 경우
				for (int j = 2; j <= rt; j++) {
					if (!(i % j))
						break;
					if (j == rt) {
						cnt++;
					}
				}
			}
		}
		cout << cnt << '\n';
		cnt = 0;
	}
}

https://codesyun.tistory.com/66?category=966171 

[BOJ / 백준] 4948번 베르트랑 공준 C++ 문제 풀이