소수 찾기

레벨 1을 어서 다 끝내야겠다는 생각으로 붙은 문제인데..

효율성에서 무너졌다.

문제는 너무 간단해서 직접 칠수 있을 정도있다.

숫자를 주면 1부터 그 숫자까지의 범위 안에서 소수를 찾아라 

예를 들어 10을 주면 2,3,5,7이 소수이므로 4를 리턴 하면 된다.

	def solution(n):
	if n == 1:
	return 0;
	if n in [2,3]:
	return 1;
	cnt = 2;
	for i in range(4, n+1):
	for j in range(2, i):
	if (i % j) == 0:
	break;
	else:
	cnt+=1
	return cnt;

view raw prime hosted with ❤ by GitHub

코드는 위와 같고 이렇게 하면 O(n^2)을 갖으며 돌아는 간다.

문제는 n의 범위가 10만까지이기에 이를 더 줄여야한다.

안그러면 시간 초과가 발생함..

사실 특정 숫자를 1부터 숫자 전까지 다 돌릴 필요가 있나 라는 생각을 하긴 했다

다만 이를 어떻게 식으로, 코드로 나타낼지 고민을 안해봐서..

여기서 잠깐 든 생각이, 배수들 중 잘 나오는수? 를 생각해보면

2, 3, 5, 7, 이렇게 말고는 없다고 판단 = > 두번째 for문의 범위를 2,3,5,7로 한정 지었다

O(N)으로 줄었지만 정답이 아예 아니다.

왜냐면 1~10이 커버칠 수 있는 제곱의 범위, 즉 120까지는 가능하나 121부터, 11, 13 등을 약수로 갖는 세자리 숫자가 등장하기 때문.

그렇다고 얘네를 모두 넣어줄 수도 없기에 결국은 일반화된 식을 찾아야만 한다.