(파이썬) 백준 1978, 2581, 11653, 1929, 4948, 9020, 1085, 3009, 4153

1978 소수찾기

n = int(input())
a = list(map(int,input().split()))
count = 0
for num in a:
    check =True
    if num <= 1:
        continue
    for i in range(2,num):
        if num%i==0:
            check = False
    if check==True:
        count+=1
print(count)

에라토스테네스의 체 방식으로 소수 구하는 방법도 있다.

( 2부터 차례대로 배수들을 다 없애는 방식)

 

2581 소수

에라토스테네스의 체 방식 사용하였음

M~N까지 이니 N포함 아래 수들의 소수 여부를 체크해서 한번에 구해줌

M = int(input())
N = int(input())
def a(n):
    arr = [False,False]+[True]*(n-1)
    m = int(n**0.5)
    for i in range(2,m+1):
        if arr[i] == True:
            for j in range(i+i,n+1,i):
                arr[j]=False
    return arr
arr = a(N)
li = []
for i in range(M,N+1):
    if i==1:
        continue
    if arr[i]==True:
        li.append(i)
if len(li)==0:
    print(-1)
else:
    print(sum(li))
    print(min(li))

 

 

11653 소인수분해

소수로 계속 나누면 소수가 아닌 수 로는 나눌 수 없게 된다.

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

 

1929 소수 구하기

에라토스테네스의 체 방식 사용하였음

a,b = map(int,input().split())

def A(n):
    arr = [False,False]+[True]*(n-1)
    m = int(n**0.5)
    for i in range(2,m+1):
        if arr[i]==True:        
            for j in range(i+i,n+1,i):
                arr[j] = False
    return arr
li = A(b)
for i in range(a,b+1):
    if li[i]==True:
        print(i)

 

4948 베트트랑 공준

에라토스테네스의 체 방식 사용하였음

def A(n):
    arr = [False,False]+[True]*(n-1)
    m = int(n**0.5)
    for i in range(2,m+1):
        if arr[i]==True:        
            for j in range(i+i,n+1,i):
                arr[j] = False
    return arr
while True:
    a = int(input())
    if a == 0: break
    if a == 1: print(1);continue
    li = A(a*2)
    count = 0
    for i in range(a+1,a*2+1):
        if li[i]==True:
            count+=1
    print(count)

 

9020 골드바흐의 추측

에라토스테네스의 체 방식 사용하였음

해당 수의 절반 부분부터 위 아래로 1씩 늘려가면서 양쪽 모두 소수인 경우를 찾으면 됨

해당 수 / 2 의 부분부터 일정한 위치에 소수가 존재한다는 원리인데 이해안감.

def A(n):
    arr = [False,False]+[True]*(n-1)
    m = int(n**0.5)
    for i in range(2,m+1):
        if arr[i]==True:        
            for j in range(i+i,n+1,i):
                arr[j] = False
    return arr
    
T = int(input())
for i in range(T):
    n = int(input())
    li = A(n)
    lenLi = len(li)-1
    halfLenArr = len(li)//2
    for z in range(halfLenArr,1,-1):
        if li[lenLi-z]== True and li[z]==True:
            print(z,lenLi-z)
            break

 

1085 직사각형에서 탈출

결국 가로나 세로의 직선으로 가야 최소 길이가 된다.

x,y,w,h = map(int,input().split())
a = w-x
b = h-y
if a>x:
    a = x
if b>y:
    b = y
if a>b:
    print(b)
else:
    print(a)

두줄

x, y, w, h = map(int, input().split())
print(min(x, y, w-x, h-y))

 

3009 네번째 점

x1,y1 = map(int,input().split())
x2,y2 = map(int,input().split())
x3,y3 = map(int,input().split())
xArr = [x1,x2,x3]
yArr = [y1,y2,y3]
for i in range(len(xArr)):
    if xArr.count(xArr[i]) == 1:
        x4 = xArr[i]
    if yArr.count(yArr[i]) == 1:
        y4 = yArr[i]
print(x4,y4)

 

4153 직각삼각형

가장 큰 수가 빗변

while True:
    a = list(map(int,input().split()))
    if sum(a)==0:
        break
    hy = max(a)
    a.remove(hy)
    if a[0]**2+a[1]**2 == hy**2:
        print("right")
    else:
        print("wrong")