소수의 개수 / c / 제한시간:1초

▣ 문제

- 자연수 N이 입력되면 1부터 N까지의 소수의 개수를 출력하는 프로그램을 작성하세요. 만약 20이 입력되면 1부터 20까지의 소수는 2, 3, 5, 7, 11, 13, 17, 19로 총 8개입니다. 제한시간은 1초입니다.

 

▣ 입력설명

- 첫 줄에 자연수의 개수 N(2<=N<=200,000)이 주어집니다.

 

▣ 출력설명

- 첫 줄에 소수의 개수를 출력합니다.

 

▣ 입력 예시

20

▣ 출력 예시

8

<내 코드>

#pragma warning(disable:4996)
#include<stdio.h>

int main() {
	int n;
	int cnt = 1;
	scanf("%d", &n);
	for (int i = 2; i <= n; i++) {
		for (int j = 2; j < i; j++) {
			if (i % j == 0) {
				cnt++;
				break;
			}
		}
	}
	printf("%d", n - cnt);
	return 0;
}

예상대로 시간초과ㅠ

<수정한 코드>

#pragma warning(disable:4996)
#include<stdio.h>

int main() {
	int n;
	int cnt = 1;
	scanf("%d", &n);
	for (int i = 2; i <= n; i++) {
		for (int j = 2; j * j <= i; j++) {
			if (i % j == 0) {
				cnt++;
				break;
			}
		}
	}
	printf("%d", n - cnt);
	return 0;
}

for (int j = 2; j * j <= i; j++)

이 부분에서 j * j를 쓴 이유는 36을 예로 들면 36 = 2 * 18 = 3 * 12 = 4 * 9 = 6 * 6 으로 표현 가능하다. 이떄 2 3 4 6만 사용해서 약수를 가지는지 확인을 하면 시간을 단축할 수 있다. 그리고 6은 36의 제곱근이므로 j * j로 표현할 수 있다.

 

Tip.

알고리즘 시간 복잡도를 계산할때

1초를 기준으로

O(N^3) 은 2560의 입력까지 가능하다.

O(N^2) 은 40960의 입력까지 가능하다.

O(NlogN) 은 대략 2천만의 입력까지 가능하다.

O(N) 은 대략 1억6천만의 입력까지 가능하다.

 

이번 문제는 수학적인 테크닉이 더 중요한듯