[C++] 소수의 개수

[목적]

자연수 N을 입력하면 1부터 N까지의 소수의 개수를 출력한다.

제한시간은 1초이다.

 

[입력 예제]

20

 

[출력 예제]

8

 

20이 입력이 되면 1부터 20까지의 소수는 [2, 3, 5, 7, 11, 13, 17, 19]로 총 8개이므로 8을 출력한다.

---

[코드]

#include <iostream>

using namespace std;

int main(void) {

    int num;
	
    cin >> num;
    int cnt=num-1;
	
    for(int i=2; i<=num; i++){
        for(int j=2; j*j<=i; j++){
            if(i%j==0) {
                cnt--;
                break;
            }
        }
    }
	
    cout << cnt;

    return 0;
}

1. 숫자를 입력받는다.

2. cnt변수에는 입력받은 숫자보다 1작은 값을 입력한다 (소수에서 1은 소수가 아니기 때문)

3. 첫번째 for문을 통해 'i'가 2부터 시작하여 입력받은 숫자까지 돌며 두번째 for문에서 소수인지 판별한다.

4. j * j가 i보다 작을 때 까지 for문을 돌려 i와 j의 모듈러 연산 값이 0이면은 소수가 아니기에 cnt값을 1 빼준 뒤 for문을 빠져나오며 다음 값을 계산한다.

5. cnt 값을 출력한다.

 

[실행 결과]

해당 사진에서는 4초가 넘게 걸렸다고 출력되었지만 채점을 돌려보면 Success가 떳다..~

 

jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=2079&sca=20

JUNGOL

[출처 - jungol]

소수의 개수를 구하는 또 다른 코드인데 시간면에서 더 좋은 코드라 생각하여 첨부한다...