[문제] 소수찾기

1부터 n 사이에 있는 소수의 갯수를 반환하는 함수 solution 을 작성해보세요.

def solution(n):
	answer = 0 # 소수의 갯수
    
    for i in range(1,n+1):
    	if i<2:
        	continue
        else:
        	for j in range(2,i): # 2부터 i 전의 숫자까지
            		if i%j==0:
                		break
    		else: # for 문을 다 실행할때까지 break되지 않았다면, 이하를 실행
            	answer+=1

처음에는 요렇게 해보았는데 맞는 코드지만 효율성 테스트에서 탈락했다.

찾아보니 '에라토스테네스의 체' 라는 알고리즘을 사용해야 한다고 해서 해당 개념을 적용시켜본다.

에라토스테네스의 체는 말 그대로 소수가 아닌 수(합성수)들을 차례로 걸러내어 소수만을 남기는 방식으로 소수를 판별해낸다.

1. 먼저 소수가 아닌 0과 1은 제외시킨다.
2. 가장 작은수인 2를 남기고 2의 배수들(합성수)을 주어진 범위 내에서 삭제한다.
3. 남아있는 수 중 가장 작은 수인 3을 남기고 3의 배수들을 삭제한다.
4. 같은 방식으로 반복한다.

코드로 아래와 같이 표현할 수 있다.

# 1부터 1000 사이의 소수를 구하려 한다
n=1000 
# 0, 1번째는 False이고 나머지는 True로 구성된 리스트를 만든다
a = [False,False] + [True]*(n-1) 

primes=[]

for i in range(2,n+1): 
  if a[i]:
    primes.append(i)
    for j in range(2*i, n+1, i):  # 2*i 부터 시작해서 n+1까지, i씩 뛰어넘으며
        a[j] = False
print(primes)

출처 - https://wikidocs.net/21638

응용해서 문제는 이렇게 풀었다.

def solution(n):
	# 먼저 2부터 입력받은 n까지 숫자를 갖는 'set'을 만든다. (차집합을 사용하기 위해)
    n_list = set([num for num in range(2,n+1)])
    
    # n_list는 계속 바뀔거기 때문에, range(2,n+1)을 기준으로 for문을 돌린다.
    for i in range(2,n+1):
        if i in n_list: # list가 아닌 set이기 때문에 요걸 해도 i를 탐색하는 것이 부담스럽지 않다.
            n_list -= set([i for i in range(i*2,n+1,i)]) # i에 해당하는 지워야 할 것들을 집합으로 만들어서 n_list에서 차집합 시행으로 없애준다! set을 사용한 이유.
            
    return len(n_list)