소수찾기

문제

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어보세요. 소수는 1과 자기 자신으로만 나누어지는

수를 의미합니다. (1은 소수가 아닙니다) 

 

제한사항

· n은 2이상 1000000이하의 자연수입니다. 

 

입출력 예 

n	result
10	4
5	3

---

풀이

1. Me

def solution(n):
    answer = 0 
    for i in range(2, n + 1): 
        if isprime(i):
            answer += 1 
    return answer 

def isprime(x):
    for i in range(2, x):
        if x % i == 0: 
            return False 
    # print('{} is Prime'.format(x))
    return True

엄청난 반복 수행으로 시간 복잡도 측면에서 통과를 못 했다.

1) 1차 시도

def solution(n):
    answer = 0 
    tmp = [i for i in range(2, n + 1) for j in range(2, i) if i % j != 0]
    answer = set(tmp)
    print(answer)
    return

2중 for문을 사용하여 소수를 구해보려 하였다. 아직 사용법이 익숙하지 않음 .. 

def solution(n):
    answer = []
    for i in range(2, n+1):
        for j in range(2, i):
            if (i % j) == 0: 
                break
        else:
            answer.append(i)
    return len(answer)

2) 2차 시도

def solution(n):
    answer = []
    for i in range(2, n+1):
        for j in range(2, i):
            if (i % j) == 0: 
                break
        else:
            answer.append(i)
    return len(answer)

2중 for문으로 구현해보았으나, 시간 초과로 인해 통과하지 못했다. 아무래도 시간 복잡도가 O(n^2)이다 보니.. ㅜ

 

2. Others

def solution(n):
    num=set(range(2,n+1))

    for i in range(2,n+1):
        if i in num:
            num-=set(range(2*i,n+1,i))
    return len(num)

에라토스테네스의 체를 구현한 코드라고 하는데, 그게 뭔지 잘 몰라 이따 살펴보려고 한다. num을 set 자료형으로 선언하고, 이후 코드는 봐도 무슨 말인지 모르겠다. 에라토스테네스의 체를 보고 오자.

---

자료 정리

1. 에라토스테네스의 체

0) 정의

-> 소수를 판별하는 알고리즘으로, 소수들을 대량으로 빠르고 정확하게 구하는 방법이다. 

1) 단일 숫자 소수 여부 확인 

-> 어떤 수의 소수 여부를 확인할 때는 해당 수를 N으로 나누면 몫이 생기는 데, 몫과 나누는 수 둘 중 하나는 

    N 제곱근 이하이기 때문에 특정 숫자의 제곱근 까지만 약수의 여부를 검증하면 빠르게 소수 여부를 구할 수 있다. 

2) 에라토스테네스의 체 원리 

-> 가장 먼저 소수를 판별할 범위만큼 배열을 할당하여, 해당하는 값을 넣어주고, 이후에 하나씩 지워나간다. 

    1. 배열을 생성하여 초기화

    2. 2부터 시작하여 특정 수의 배수에 해당하는 수를 모두 지움 (지울 때 자기 자신과 이미 지워진 수는 pass) 

    3. 2부터 시작하여 남아있는 수를 모두 출력한다. 

3) 에라토스테네스의 체 대표적인 코드 

n=1000
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):
        a[j] = False

print(primes)