[프로그래머스]기사단원의 무기/python

👾(Lv.01)기사단원의 무기
https://school.programmers.co.kr/learn/courses/30/lessons/136798

🖥️답안

def solution(number, limit, power):
    l=[0]*(number+1)
    for i in range(1,number+1):
       for j in range(1,int(i**(1/2)+1)):
            if i%j==0:
                index = 2 if j != i/j else 1
                l[i] += index
                
        if l[i]>limit:
            l[i]=power
            
                      
    return sum(l)

💡배운점

에라토스테네스의 체

소수를 판별하는 알고리즘

하나씩 확인하는 방법

def is_primenum(x): #x가 소수인지 확인하는 알고리즘
    for i in range(2, x):
    	if x % i == 0:
        	return False
    return True

👉🏻 시간복잡도 O(n)

이런 방식으로 1~10 사이의 수중에서 소수인 수를 찾으려면 시간복잡도가 O(n²)로 기하급수적으로 늘어난다🫠

처음에 이런 방식으로 풀다가 문제를 틀렸다

에라토스테네스의 체로 확인하는 방법

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

👉🏻 시간복잡도 O(sqrt(n))