[파이썬] 12. 기본수학...백준(1978, 2581, 11653, 1929)

[1978] 소수 찾기

해결 포인트

소수란... 1과 자기자신으로만 나울 수 있는 수를 말한다.

그럼 2부터 자기자신-1 까지 수를 돌리며 나눴을때 나머지를 확인하여 소수를 판별 한다는 것이 생각날것이다.

답안

a = int(input())
b = list(map(int,input().split()))
cnt = 0
def find(a):
  if(a<2):
    return False
  for i in range(2,a):
    if(a%i==0):
      return False
  return True
for j in b:
    if find(j):
        cnt += 1
print(cnt)

 

 

[2581] 소수

해결 포인트

이전 문제와 매우 유사하다.

range의 값을 조금 수정했고,

합은 sum

최솟값은 min을 이용하면 된다.

소수가 없을 경우까지 고려하여 구현했다.

답안

a = int(input())
b = int(input())
li = []
def find(v):
    if v < 2:
        return False
    for j in range(2,v):
        if v % j == 0:
            return False
    return True
for i in range(a,b+1):
    if find(i):
        li.append(i)
if len(li) != 0:
    print(sum(li))
    print(min(li))
else:
    print("-1")

[11653] 소인수분해

해결 포인트

소인수분해에 대해 수학적으로 우선 접근하여
로직을 생각해보자

답안

a = int(input())
b = 2
while a != 1:
    if a % b !=0:
        b += 1
    else:
        print(b)
        a = a/b

입력받은 a 값을 2로 나누어 나머지가 0일때 출력하고 그렇지 않다면 b를 +1시켜 다시 나눠 나머지를 확인한다.

나머지가 0이 돨때마다 a에는 a/b의 값을 다시 넣어줘야 한다.

 

[1929] 소수 구하기

해결 포인트

해당 문제는 시간 제한이 걸려있다.

아무리 머리를 쥐어짜도... 잘 생각이 안났고 sqrt 함수를 알게돠어 사용했다.

포문의 범위를 절반 이하로 줄여 시간 내에 해결 가능했다.

답안

import sys
import math
input = sys.stdin.readline()
a,b = map(int,input.split())
def find(v):
    if v < 2:
        return False
    for i in range(2,int(math.sqrt(v)+1)):
        if v % i == 0:
            return False
    return True
for j in range(a,b+1):
    if find(j):
        print(j)

import math가 필요하다.

기본 로직은 이전 문제들과 똑같으나...

for문 range를 살펴보면 math.sqrt(v)+1가 있다. 이는 정수 v의 제곱근을 수하는 함수이며

이를통해 for문 범위를 대폭 줄여 빠르게 계산이 가능하다.

 

점점 벽을 느끼고있다..

다시한번 기초문법을 공부할 예정이다...