[프로그래머스] Lv 1. 소수 찾기(Python3)

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

 

문제

1부터 입력 받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 봅시다.

 

풀이

해당 숫자가 소수인지 판단하는 알고리즘 중 가장 빠른 알고리즘은 해당 숫자의 √N 까지만 확인하는 방법입니다.

import kotlin.math.*

fun isPrime(num: Int): Boolean {
	for (i in 2 .. sqrt(n)) {
    	if (num % i == 0) return false
    }
    return true
}

 

입력 값이 크지 않으니, 2부터 n까지 반복문을 수행하여 해당 숫자가 소수인지 판단하는 방식으로 풀어도 시간 내에 풀 수 있습니다.😄

 

코드

import math

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

def isPrime(n):
    sqrt = int(math.sqrt(n))
    for i in range(2,sqrt+1):
        if n % i == 0:
            return False
    return True