소수 찾기

이번문제는, 0~N사이의 소수의 개수를 찾는 문제입니다.

https://programmers.co.kr/learn/courses/30/lessons/12921

코딩테스트 연습 - 소수 찾기

일단, 소수는 규칙이 없습니다.

 

때문에, 컴퓨터에서 소수 여부를 확인할라면, N을 나눠서 나머지가 0인 숫자가 있는지를 전부 확인해야합니다

(정확히는 N^(1/2)까지)

https://teus-kiwiee.tistory.com/61?category=914262 

Prime Number 여부 확인(단순탐색)

이번 문제에서 단순탐색으로 1.소수여부를 확인 -> 2.아니면 삭제

를 할 경우 당연히 효용성 테스트를 통과하지 못합니다.

 

소수의 규칙은 모르지만, 소수가 아닌 값을 소거법으로 제거하는 방법으로 "에라톤스테너의 체" 가 있습니다

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

논리는 굉장히 간단합니다.

1. 2부터 주어진 N까지의 값을 갖는 List를 생성한다

2. 2를 제외하고 2의 배수를 모두 제거한다

3. 2+n이 List에 있는지 확인하고, 없으면 (2+n)의 배수를 모두 제거한다

간단히 보면

 

해당 숫자가 소수인지 판별하지 않고

 

다른 수의 배수인 경우를 모두 제외하는 소거법 형태로 소수여부를 판단하게 됩니다.

 

Python의 경우 Set이 집합을 추상화 하여서, 차집합을 구할 수가 있습니다.

import copy
def solution(n):
    answer = 0
    #효율성을 위해서, List를 생성할 때 기본적으로 2의 배수를 다 제거
    c_answer = {i for i in range(2, n+1) if (i == 2 or i%2!=0)}        
    for i in range(3, n+1):                             
        #2+n의 값이 존재하는지 여부를 확인
        if i in c_answer:
            #2+n이 있을 경우, 2+n의 배수 집합을 생성
            temp = {j for j in range(2*i, n+1, i)}                
            #요러면 효율성 테스트를 통과
            c_answer -= temp          
            #아래와 같은 코드의 경우 효율성 테스트를 통과 X
            #이유는 모르겠지만, -= operand대비 10배의 시간 소요
            #c_answer = c_answer - temp          
    return len(c_answer)