소수 찾기 (문제 개편 후)

프로그래머스 lv0 소수 찾기 파이썬

📚 문제

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

🥳 해결

우선 소수를 얻는 방법 에 대해서 생각해봐야한다.
특히 이 문제는 효율성 검사도 같이 하기 때문에 빠르고, 간단하게 코드를 짜야했다.

이 말은 즉슨, 간단하게 for문을 돌려서 나눠지는 가능성을 일일히 계산하는
경우에는, 시간과 효율성 때문에 통과되지 않는다는 얘기다.
어떻게 아느냐고요? 저도 알고 싶지 않았습니다.

해결 (1) - 실패

실패 예시 (1)

def solution(n):
    ans = 0
    for i in range(2, n+1):
        num = int(n ** (0.5))+1
        
        for j in range(2, num):
            if i % j == 0:
                break
            ans += 1

    return ans

우선 나는 def 함수를 2개 만들었다.
이유는 if 문에 일일히 넣는경우, for문을 사용했기에,

ex) def solution(10) = 6 ([3, 5, 5, 7, 7, 9]) (9는 처음에 2로 나뉘지 않기 때문에 한번 들어갔다.)

이처럼 시도한 횟수 만큼 a가 +가 되는것처럼 짜지기 때문이었다.

해결 (2) - 성공

def isprime(num):
        number = int(num**(0.5)+1)
        for i in range (2, number):
            if num % i == 0:
                return 0
        return 1

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

앞서 말한 바와 같이 효율성과 시간의 단축 해결을 위해서는 큰 숫자가 들어와도 작동 횟수가 적고 간단해야한다.

 1. 1부터 본인인 n을 곱하기 보다는 나눠지기가 가능한 수는 그 수의 루트 
    라는 점을 이용.
 2. 1은 소수가 아니기 때문에 for문에서 1을 제외.

이렇게 성공! 휴;;

해결 - 성공(2)

이건 추가적으로 방법을 찾은것으로 나중에 도움이 될것 같아서 기록용...

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

    for j in range(2,n+1):
        if j in array:
            array -= set(range(2*j,n+1,j))
    a = len(array)
    return a

조금 찾아보니.. 에라토스테네스의 체 라고 소수를 판별하는 법이 있었다.

set으로 바꾼것은 -= 연산자를 사용하기 위해서다.
list로 풀려고 하다가...정말 멀리멀리 돌아갈 뻔했다.

-= 연산 후 존재하지 않는다면 (배수라면) 패스하고 다음 숫자로 가는 형식...

에라토스테네스의 체

에라토스테네스의 체

소수를 판별하는 방법으로, 배열을 생성 후, 
2부터 시작해 본인을 제외한 배수의 수는 배열에서 삭제 하고, 
이 과정을 반복하면서 남은 수(소수)를 출력하는 것이다.

 	코딩은 수학적 사고 능력이 좋아야 한다는 이유를 조금...알것 같다  
    그래도 오늘 방법을 하나 더 배워서 조금 뿌듯...