[인프런 C++] 15. 소수의 개수

자연수 N이 입력되면 1부터 N까지의 소수의 개수를 출력하는 프로그램을 작성하세요.

만약 20이 입력되면 1부터 20까지의 소수는 2 3 5 7 11 13 17 19로 총 8개 입니다. 

제한시간은 1초입니다.

 

입력

20

 

출력

8

 

1트 (성공) 데이터가 크면 제한시간에 맞추지 못한다.

#include <iostream>
using namespace std;

bool isPrime(int x){
	bool isPrime = true;
	for(int i = 2; i < x; i++){
		if(x%i == 0){
			isPrime = false;
		}
	}
	
	return isPrime;	
}

int main(void){
	int n, cnt;
	
	cin >> n;
	for(int i = 2; i <= n; ++i){
		if(isPrime(i)){
			cnt++;
		}
	}
	
	cout << cnt;
	return 0;
}

 

 

2트 (강의 해설)

i * i <= x

주어진 값의 반만(제곱근) 확인해도 괜찮다. 반만큼의 약수가 더 있다는 것은 필연적이기 때문이다.

#include <iostream>
using namespace std;

int main(void){
	int n, cnt = 0;
	cin >> n;

	for (int i = 2; i <= n; ++i) {
		bool isPrime = true;
		for (int j = 2; j * j <= i; ++j) {
			if (i % j == 0) {
				isPrime = false;
				break;
			}
		}

		if (isPrime) cnt++;
	}
	
	cout << cnt;
	return 0;
}