Baek Junアルゴリズム第8ステップ(エラトネスの体)

新規コンテンツ

1）1978号小数点を検索する

少数の規則性を先にグーグル化したが、完璧な規則性はまだ存在しない.
したがって、入力値が1000以下であるため、ランタイムエラーが発生しない場合は、入力値を下回らない整数に分割することが少なくない.

N = int(input())
nums = list(map(int, input().split()))
cnt = 0

for num in nums:
    cnt += 1
    if num > 2:
        for i in range(2, num):
            if num % i == 0:
                cnt -= 1
                break
    # 단 1, 2는 별도로 판단했다.
    elif num == 1:
        cnt -= 1
    elif num == 2:
        continue

print(cnt)

2）2581回少数判別

方式は以上の通り.

N = int(input())
M = int(input())
ansList = list()

for i in range(N, M+1):
    if i == 2:
        ansList.append(2)
    else:
        for r in range(2,i):
            if i % r == 0:
                break
            if r == i-1:
                ansList.append(i)

if len(ansList) != 0:
    print(sum(ansList))
    print(min(ansList))
else:
    print(-1)

3）11653号素数分解

正解を提出して処理するのに時間がかかったようですが、実行時にエラーは発生しませんでした.

N = int(input())

i = 2
#입력값이 1이면 무시
if N == 1:
    pass
else:
    while i <= N:
        if N % i == 0:
            print(i)
            N = N / i
        else:
            i += 1

4)1929回小数を求める(エラトネスの体アルゴリズム)

タイムアウトの問題でずっと困っていた問題...!
最後に劇的に重複文を消し、答えを得た.
このことから,エラトネスの体は所与の範囲内で少数を判別する最も有効な方法であることが分かった.

以上の理論によれば,小数を判別するためには,すべての数の倍数をnで割る必要はなく,nの二乗で割るだけで十分であることが分かる.
これを利用して2回目の試みを行いましたが、重複文のためか時間がかかり、重複文を削除して関数を呼び出すことで変更し、最終的に正しいコードを得ました.
注意:https://namu.wiki/w/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98%20%EC%B2%B4

# 시간 초과 난 제출 코드...!
M, N = map(int, input().split())
all_list = list(range(M, N + 1))
k = 2
for i in range(N-M+1):
    if all_list[i] == 0:
        continue
    scope = int(N/k)
    for j in range(2, scope + 1):
        if (j*k) in all_list:
            idx = all_list.index(j*k)
            all_list[idx] = 0
    k += 1

cnt = all_list.count(0)
for t in range(cnt):
    all_list.remove(0)

for u in range(len(all_list)):
    print(all_list[u])

# 시간초과 2.. 반복문의 범위를 제곱근의 크기로 줄였으나 여전히 시간초과
M, N = map(int, input().split())
all_list = list(range(M, N + 1))
ans_list = list()
for i in all_list:
    ans_list.append(i)
    for j in range(2, int(i**0.5)+1):
        if i % j == 0 and i != j:
            ans_list.remove(i)
            break
if 1 in ans_list:
    ans_list.remove(1)
for t in range(len(ans_list)):
    print(ans_list[t])

# 시간 초과를 피하고자 이중 반복문을 제거하고 함수 호출 방식을 택했다.
M, N = map(int, input().split())

def primeCheck(num):
	# 입력값이 1이라면 바로 False 리턴
    if num == 1:
        return False
    # 아닌 경우에는 입력값의 제곱근 + 1만큼만 반복을 돌아 판별
    else:
        for i in range(2, int(num**0.5)+1):
        	# 만약 나누어 떨어진다면 False 리턴
            if num % i == 0:
                return False
        # 모두 나누어 떨어지지 않았다면 True 리턴
        return True

for i in range(M, N+1):
    if primeCheck(i) == True:
        print(i)

5)4948番バートラン姫

入力したnと2 nの間の小数を決定します.
ただし、入力値が0になるまで文のループを続けるとタイムアウトします.
したがって、所定の範囲で対応する小数点リストを格納することができる.
小数点リストの入力範囲に対応するelementカウント出力

#소수 체크 함수
def primeCheck(num):
    if num == 1:
        return False
    else:
        for i in range(2, int(num ** 0.5) + 1):
            if num % i == 0:
                return False
        return True
#주어진 모든 범위
all_list = list(range(2, 246912))
prime_list = []

#주어진 모든 범위 내 소수만을 담은 리스트 prime_list
for k in all_list:
    if primeCheck(k) == True:
        prime_list.append(k)

#반복문 내부에서는 이미 만들어진 리스트 내부 값으로만 판별한다.
while True:
    n = int(input())
    cnt = 0
    if n == 0:
        break
    for j in prime_list:
        if n < j <= 2*n:
            cnt += 1
    print(cnt)

6）9020号金バッハの推測

推測:入力された偶数の値は2つの小数とから構成できます.
小数点以下と構成の差が最小の

# 소수 판별 함수
def primeCheck(num):
    if num == 1:
        return False
    else:
        for i in range(2, int(num ** 0.5) + 1):
            if num % i == 0:
                return False
        return True
# 입력 받을 수 있는 범위
all_list = list(range(2, 10000))
# 범위 내 소수만을 담을 리스트
prime_list = []

for k in all_list:
    if primeCheck(k) == True:
        prime_list.append(k)

T = int(input())
for _ in range(T):
    n = int(input())
    check_idx = 0
    fir = 0
    for j in prime_list:
        if j >= int(n/2):
        	# 입력 받은 수의 1/2보다 첫번 째로 큰 값을 fir에 담아줌
            fir = j
            check_idx = prime_list.index(fir)
            break
    idx = 1
    while True:
    	# 입력 받은 수에서 fir를 빼주면 sec
        sec = n - fir
        # sec가 소수 리스트에 있다면 조건 성립
        if sec in prime_list:
            if fir > sec:
                print(str(sec) + ' ' + str(fir))
            else:
                print(str(fir) + ' '+ str(sec))
            break
        else:
            fir = prime_list[check_idx - idx]
            idx += 1

7）1085号矩形から脱出

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

a = w - x
b = h - y

# 경계선 까지의 4가지 루트 거리를 담은 리스트
ans_list = [x, y, a, b]

print(min(ans_list))

8）3009号第四点

x1, y1 = map(int,input().split())
x2, y2 = map(int,input().split())
x3, y3 = map(int,input().split())

x_list = [x1, x2, x3]
y_list = [y1, y2, y3]

# 리스트에 중복되지 않은 수가 네번째 점의 좌표값이다!
for i in x_list:
    if x_list.count(i) == 1:
        x4 = i
        break

for j in y_list:
    if y_list.count(j) == 1:
        y4 = j
        break
print(str(x4)+ ' '+ str(y4))

9)4153号直角三角形(ピタゴラスの定理)

while True:
    a, b, c = map(int, input().split())
    if a == b == c == 0:
        break

    check_list = [a, b, c]
    # 가장 큰 element를 따로 저장하고 리스트에서 제거
    maxElement = max(check_list)
    check_list.remove(maxElement)
	
    #이를 활용하여 피타고라스 정리 (a^2 + b^2 = c^2)
    if (maxElement ** 2) == (check_list[0] ** 2) + (check_list[1] ** 2):
        print('right')
    else:
        print('wrong')

10）3053号タクシー幾何学

タクシージオメトリにおける2点(T 1(x 1,y 1)とT 2(x 2,y 2)との距離Dは
D(T 1,T 2)=x 1−x 2ㅤ+x 2−y 2として定義される.
そのため、タクシーの通学時の円はダイヤモンドの形をした正方形になり、幅は
2*R^2.(正方形の幅)

ソース:https://ahdelron.tistory.com/m/41

import math

R = int(input())
uclid = R**2 * math.pi
taxi = 2 * (R**2)

print(f'{uclid:.6f}')
print(f'{taxi:.6f}')

11）1002号タワー

2つの円の原点座標と半径の長さを入力して、2つの円の位置関係の質問をします.したがって、原点間の距離と半径の和に基づいて判別する条件文を作成する必要があります.

T = int(input())

for i in range(T):
    x1, y1, r1, x2, y2, r2 = map(int, input().split())
    # 만약 두 사람의 좌표와 반지름이 길이가 같다면 류재명 위치의 개수는 무한대
    if x1 == x2 and y1 == y2 and r1 == r2:
        print(-1)
        # 다음 케이스로 넘어가기 break는 반복문 아예 종료
        continue
    # 원 간의 위치관계 ( d는 두 사람간 거리)
    d = (((x1 - x2) ** 2) + ((y1 - y2) ** 2)) ** 0.5
    if r1 + r2 == d:
        print(1)
    elif r1 + r2 < d:
        print(0)
    # 어떤 값이 더 큰지 모르니 절댓값 처리 abs()
    elif abs(r1 - r2) < d < r1 + r2:
        print(2)
    elif abs(r1 - r2) == d:
        print(1)
    elif abs(r1 - r2) > d:
        print(0)