백준(4948번 베르트랑 공준)풀이 C++

www.acmicpc.net/problem/4948

4948번: 베르트랑 공준

1) 주석 없는 VERSION

#include <iostream>
#include <cmath> 
#include <cstdio>

using namespace std;

int main() {
	long long n, test, i, j;
	long long cnt = 0;

	while (1) {
		cnt = 0;
		cin >> n;
		if (n == 0) break;

		else if (n == 1) cout << "1"<<"\n";
		
		else {
			for (int i = n + 1;i <= 2 * n;i++) {

				if (i % 2 != 0) {

					for (int j = 3;j <= sqrt(i);j+=2) {
						if (i % j == 0) {
							cnt--;
							break;
						}
					}
					cnt++;
				}

			}
			cout << cnt << "\n";
		}

	}

}

 

2) 주석 있는 VERSION

 

시간초과 주의

 

#include <iostream>
#include <cmath> 
#include <cstdio>

using namespace std;

int main() {
	long long n, test, i, j;
	long long cnt = 0;

	while (1) {
		cnt = 0;
		cin >> n;

		//0이 입력될 때까지 반복
		if (n == 0) break;

		//1일 경우 1출력
		else if (n == 1) cout << "1"<<"\n";
		
		else {
			for (int i = n + 1;i <= 2 * n;i++) {

				//짝수는 소수가 아니므로 한번 걸러주기
				if (i % 2 != 0) {

					//j+=2 주의하기
					//에라토스테네스의 소수 필요 충분조건사용
					for (int j = 3;j <= sqrt(i);j+=2) {

						// 2보다 크면서 자기 자신의 제곱근까지의 수에 나누어지지 않는 수가 소수
						if (i % j == 0) {
							cnt--;
							break;
						}
					}
					cnt++;
				}

			}
			cout << cnt << "\n";
		}

	}

}