소수의 개수 ( 1초 시간제한 ) C++

1초에 20만의 숫자도 소수인지 판별하기 위해서는 for문에서 소요되는 시간을 줄여야한다.

36을 예로 들었을 때,

1 * 36

2 * 18

3 * 12

4 * 9

6 * 6 이다.

즉, 36의 제곱근까지만 확인해도 소수인지 알 수 있다.

sqrt 함수를 사용해도 되지만 j*j==i 구문을 사용하여 제곱근처럼 사용한다.

 

#include<stdio.h>

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