[ 프로그래머스 / 파이썬 ] 소수 찾기 (제곱근, 에라토스테네스의 체)

# 소수 찾기

• 시간초과 1) 그냥 풀기 -> 테케 정확도 10,11,12 / 효율성 1,2,3,4 탈

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

• 시간초과 2) 제곱근 사용하기 -> 테케 정확도 11 / 효율성 1,2,3,4 탈
  • 'N의 약수는 무조건 sqrt(N) 범위에 존재한다' 를 적용

def solution(n):
    answer = 0
    for num in range(2,n+1):
        count = 0
        for i in range(2,int(num**(0.5))+1):
            if num%i == 0:
                count+=1
        if count == 0:
            answer+=1
                
    return answer

• 성공 ) 에라토스테네스의 체 사용
  • 소수(x)의 배수는 약수로 무조건 x를 포함하게 된다.
    따라서 절대 소수의 배수는 소수가 될 수 없다. 이를 이용한 것이 에라토스테네스의 체이다.
    누구나 알고있는 가장 작은 소수인 2부터 시작해서, 2의 배수를 다 지웠으면, 지워지지 않은 수 중에서 다음 값인 3의 배수를 지워나가고 이를 계속해서 반복해 나가면 소수만 남게된다.
    마치 체에 걸러서 남는 것들만 뽑아내는 방식이라고 생각하면 된다.

def solution(n):
    answer = 0
    n += 1                            # for문 사용을 위한 n += 1
    prime = [True] * n                # n개의 [True]가 있는 리스트 생성
    for i in range(2, int(n**0.5)+1): # n의 제곱근까지만 검사
        if prime[i]:                    # prime[i]가 True일때
            for j in range(2*i, n, i):    # prime 내 i의 배수들을 False로 변환
                prime[j] = False

    for i in range(n):              # 소수 카운팅
        if i > 1 and prime[i] == True:  
            answer+=1
                
    return answer

 

+ (GOOD) 풀이 set을 사용한 에라토스테네스의 체

• 2~n까지의 수를 함수 num에 담기
• 2~int(n**0.5)+1까지의 수 i 에 대해, i 가 num 안에 있으면, i의 배수set(i의 2배수 부터 n까지수 중 i 만큼 간격있는 수들)를 num에서 빼주기
• 나머지 num의 길이 리턴

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

 

 

# 서울에서 김서방 찾기

def solution(seoul):
    return '김서방은 ' + str(seoul.index('Kim')) + "에 있다"

 

# 이상한 문자 만들기

• 공백 처리에 주의할 것 

def solution(s):
    answer = ''
    count = 0
    for a in s:
        if a==" ":
            answer+=" "
            count=0
        else:
            count+=1
            if count%2==0:
                answer+= a.lower()
            else:
                answer+= a.upper()

    return answer

 

# 정수 제곱근 판별

def solution(n):
    answer = 0
    j = n**(1/2)
    if j == int(j):
        answer = (j+1)**2
    else:
        answer = -1
    return answer