[프로그래머스] [Level 1] 소수 찾기

문제) 소수 찾기

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

 

• 내 풀이 ( 전부 오답: 시간 초과) : 처음으로 풀지 못한 문제가 되었다..

• 첫 번째 풀이

def solution(n):
    answer=0
    for i in range(2,n+1):
        #나눴을 때 나머지가 0이 나오는 값은 1과 자기자신 -> 2개
        ls = [ i for x in range(1,i+1) if i%x==0]
        if len(ls)==2:
            answer+=1
    return answer

• 두 번째 풀이

- 짝수 세지 않기

- i가 2,3,5,7일 경우는 따로 조건 두기

- i가 2,3,5,7로 나눠지는 경우 고려X

- i가 제곱수일 경우 고려X

→ 시간 효율 높임 but 그래도 시간 초과

def solution(n):
    answer=0
    if n>=2:
        #소수 2
        answer+=1
        #짝수는 소수가 아니므로 세지 않음
        for i in range(3,n+1,2):
            cnt=0
            if i==2 or i==3 or i==5 or i==7:
                answer+=1
            if i%2==0 or i%3==0 or i%5==0 or i%7==0:
                    continue
            elif i**(1/2)==int(i**(1/2)):
                    continue
            #i-1 값까지 나눴을 때 나머지가 0이 나오는 값은 1 -> 1개
            for x in range(1,i,2):
                if i%x==0:
                    cnt+=1
            if cnt==1:
                answer+=1
    return answer

 

 

• 다른 사람 풀이

- 나누는 값을 제곱근 까지만 나누는게 정답 포인트!!

- 모든 수만큼 answer+1 하면서 약수가 있는 경우 answer-1

def solution(n):
    answer=0
    for i in range(2,n+1):
        if i==2:
            answer+=1
            continue
        for j in range(2,int(i**0.5)+1):
            if i%j==0: #i의 제곱근 이하의 약수가 있으면 삭제
                answer-=1
                break
        answer+=1
    return answer

 

→ 위의 풀이를 조금 더 시간 효율적으로 변경한 코드

- 짝수의 경우를 고려하지 X

def solution(n):
    answer=0
    if n>=2:
        answer+=1 #2일 경우
        #짝수일 경우는 고려X
        for i in range(3,n+1,2):
            for j in range(3,int(i**0.5)+1,2):
                if i%j==0: #i의 제곱근 이하의 수 중에 약수의 경우
                    answer-=1
                    break
            answer+=1
    return answer

 

• 다른 사람 풀이2

def solution(n):
    tf=[True]*(n+1)
    m= int(n**0.5) #n의 제곱근
    for i in range(2,m+1): 
        if tf[i]==True:
            for j in range(i*i,n+1,i):
                #i제곱 이상의 i의 배수 값들 false처리
                tf[j]=False
        
    x=[i for i in range(2,n+1) if tf[i]==True]
    
    return len(x)

print(solution(10))
#결과
4