합성수 찾기

https://school.programmers.co.kr/learn/courses/30/lessons/120846

파이썬

에라토스테네스의 체

def solution(n):
    primes = [True for _ in range(n + 1)]
    primes[0] = primes[1] = False
    for num in range(2, n):
        if primes[num]:
            for each in range(num * 2, n + 1, num):
                primes[each] = False
    return n - sum(primes) - 1

 

'에라토스테네스의 체'를 쓰지 않고... 

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

 

다중 for문은 읽기 불편하다. 

함수가 여러 기능을 가지고 있는 경우는 분리하면 좋다. 

 

이 함수는
소수를 찾는 기능과 집계 기능
두 가지를 가지고 있다.

cf) 만약 x, y 좌표를 전수조사(BF) 하기 위해
이중 for문을 사용하는 경우는
분리하지 않는 게 좋을 것이다. 

함수의 이름은 동사가 좋다.

무언가를 체크할 때는 is나 check 등의 접두사가 어울린다.  

def is_composite(n):
    counter = 0
    for i in range(1, n + 1):
        if n % i == 0:
            counter += 1
    if counter > 2:
        return True
    else:
        return False


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


print(solution(10))
print(solution(15))

 

if문을 가볍게...

def is_composite(n):
    counter = 0
    for i in range(1, n + 1):
        if n % i == 0:
            counter += 1
    if counter > 2:  # 이 조건문이 성립하면 함수가 종료된다. (True 반환)
        return True
    return False  # 위 조건 문이 성립하지 않는 경우에만 이 리턴문이 실행된다. 
    # 그래서 else 문을 생략할 수 있다.


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


print(solution(10))
print(solution(15))

 

if문을 가볍게.. 2

def is_composite(n):
    counter = 0
    for i in range(1, n + 1):
        if n % i == 0:
            counter += 1
    return counter > 2  # 'counter > 2' 조건이 맞으면 True 틀리면 False 이다.


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


print(solution(10))
print(solution(15))

 

합성수를 찾는 함수의 업그레이드 1

1과 자기 자신은 무조건 약수.
이를 제외한 약수를 찾는 것이 좋다. 

def is_composite(n):
    for i in range(2, n):
        if n % i == 0:
            return True
    return False


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


print(solution(10))
print(solution(15))

 

합성수를 찾는 함수의 업그레이드 2

끝까지 조사할 필요가 없다. 

제곱근까지만 검사하고, 
중간에 합성수를 찾으면
바로 True를 돌려주고 종료.

에라토스테레스의 체를 이용하지 않는다면
아마 이게 베스트일 것이다. 

def is_composite(n):
    for i in range(2, int(n ** .5) + 1):
        if n % i == 0:
            return True
    return False


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


print(solution(10))
# print(solution(15))

 

for문을 가볍게... 1

조건을 만족할 때 1을 더하는 유형의 for문은
sum과 리스트 컴프리헨션, 또는 제너레이터 익스프레션을 이용하면
간단하게 표현할 수 있다. 

여기까진 읽기 괜찮은 것 같다.
(업그레이드 전의 합성수 찾기 함수를 사용)

def is_composite(n):
    counter = sum(1 for i in range(1, n + 1) if n % i == 0)
    return counter > 2


def solution(n):
    return sum(1 for i in range(1, n + 1) if is_composite(i))


print(solution(10))
print(solution(15))

 

가독성이 ㅠ,.ㅠ 

def solution(n):
    def is_composite(x):
        return 2 < sum(1 for i in range(1, x + 1) if x % i == 0)

    return sum(1 for i in range(1, n + 1) if is_composite(i))


print(solution(10))
print(solution(15))

가독성 따윈... 코테는 이맛이지...

def solution(n):
    return sum(1 for i in range(1, n + 1) if (lambda x: 2 < sum(1 for j in range(1, x + 1) if x % j == 0))(i))

print(solution(10))
print(solution(15))

 

이렇게 쓰면 안됨

solution = lambda n: sum(1 for i in range(1, n + 1) if (lambda x: 2 < sum(1 for j in range(1, x + 1) if x % j == 0))(i))

https://peps.python.org/pep-0008/#programming-recommendations

Always use a def statement 
instead of an assignment statement 
that binds a lambda expression directly to an identifier.

람다를 변수에 바로 어사인(assign, bind, =)하지 말고, def 문을 쓰세요~!

람다를 변수에 바로 어사인할 경우 람다의 장점은 사라지고,
에러 검출 과정이나 메모리 관리 등에 불편함을 만들 뿐이므로 사용하지 않는 게 좋다. 

https://youngwonhan-family.tistory.com/entry/python-lambda-%EA%B8%B0%EC%B4%88-%ED%99%9C%EC%9A%A9%EB%B2%95

https://newbiecs.tistory.com/332

https://frhyme.github.io/python-basic/python_difference_bet_lambda_def/

 

코틀린

class Solution {
    fun solution(n: Int): Int {
        val sieve: Array<Boolean> = Array(n + 1) { _ -> true }
        var counter = 0
        for (i in 2..n) {
            if (sieve[i]) {
                counter++
                for (j in (i * 2)..n step i)
                    sieve[j] = false
            }
        }
        return n - counter - 1
    }
}