합성수 찾기
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://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
}
}