[알고리즘]기초2-소수 찾기

소수 찾기

https://programmers.co.kr/learn/courses/30/lessons/12921

첫 번째 코드

def solution(n):
    answer = 0
    for i in range(2,n+1):
        temp=True
        if i==2:
            temp=True
        else:
            for j in range(2,i):
                if i%j==0:
                    temp=False
                    break;
        if temp==True:
            answer+=1
    return answer

단순반복문을 이용하여 숫자의 처음부터 끝까지 나누어떨어지는 숫자가 있는지 여부를 판단
👉🏻 시간초과로 통과되지 못했다.

두 번째 코드

import math

def solution(n):
    answer = 0
    for i in range(2,n+1):
        temp=True
        if i==2:
            temp=True
        else:
            for j in range(2, round(math.sqrt(i))+1):
                if i%j==0:
                    temp=False
                    break;
        if temp==True:
            answer+=1
    return answer

👉🏻이중 for 문의 내부에 서 반복문의 범위를 주어진 수의 제곱근까지로 좁힘(약수는 제곱근을 기준으로 짝을 이루므로 제곱근까지만 나누어떨어지는지 판별하면 그 이후의 숫자는 확인할 필요가 없기 때문에)