■ 백준 1934 최소공배수_브론즈 1 (복습)
- 유클리드 호제법
- a와 b의 최대공약수 == b와 a%b(=나머지)의 최대공약수
- a에 b를 대입하고 b에는 a%b(=나머지)를 대입하다 보면 언젠가 a%b == 0이 됨
- 그때 b는 a,b의 최대공약수
- 최소공배수는 최초 a * b에 최대공약수를 나눈 값
# (복습)_기존 코드 시간 4248ms 실화냐
# import sys
# for i in range(int(input())):
# a, b = map(int, sys.stdin.readline().split())
# mul = 1
# for i in range(2, int((a*b)**0.5)+1):
# while a%i == 0 and b%i == 0:
# mul *= i
# a //= i
# b //= i
# print(mul*a*b)
# 고수코드: 유클리드 호제법을 사용 (이런게 있는지 몰랐다..)
import sys
T=int(input())
for i in range(T):
a,b=map(int,sys.stdin.readline().split())
aa,bb = a,b
while a%b!=0:
a,b = b,a%b
print(aa*bb//b)
■ 백준 13241 최소공배수_실버 5
# 위 문제가 거의 똑같지만 약간의 피드백이 있다.
# while의 조건을 간단하게!
a, b = map(int, input().split())
x, y = a, b
while b:
a, b = b, a%b
print(x*y//a)
■ 백준 1735 분수 합_실버 3
a, b = map(int, input().split())
c, d = map(int, input().split())
bottom = b*d
top = a*d + c*b
x, y = top, bottom
while bottom:
top, bottom = bottom, top%bottom
print(x//top, y//top)
■ 백준 2485 가로수_실버 4
def gcd(x, y):
while y:
x, y = y, x%y
return x
n, *a = open(0).read().split()
a = list(map(int, a))
a_ = [a[i]-a[i-1] for i in range(1, len(a))]
# 두 수의 최대공약수를 나머지 다른 수와 계속 최대공약수를 구해나가면 모든 수의 최대공약수가 된다.
gcd_all = a_[0]
for i in range(1, len(a_)):
gcd_all = gcd(gcd_all, a_[i])
print((a[-1] - a[0])//gcd_all-(len(a)-1))
# # 고수코드: math 모듈을 썻네...? 그 외에 첫 항을 따로 변수 저장해서 활용하는게 인상깊었다.
# import math
# a,b,*n=map(int,open(0).read().split())
# print((n[-1]-b)//math.gcd(*[i-b for i in n])-len(n))
■ 백준 4134 다음 소수_실버 4
def isPrime(x):
if x < 2: return 0
for i in range(2, int(x ** 0.5) + 1):
if x % i == 0: return 0
else: return 1
import sys
t = int(sys.stdin.readline())
for _ in range(t):
n = int(sys.stdin.readline())
while isPrime(n) == 0:
n += 1
print(n)
# #고수코드: 솔직히 이해 못하겠다.
# def t():
# h = list(map(int, open(0).read().lstrip("0123456789").split()))
# e = []
# for q in h:
# while not u(q): q += 1
# e.append(q)
# print("\n".join(map(str, e)))
#
#
# def u(i):
# c = (2, 3, 61)
# if i <= 66: return i in (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61)
# k = i - 1;
# b = 0
# while k % 2 == 0: k //= 2;b += 1
# for r in c:
# o = pow(r, k, i)
# if o == 1 or o == i - 1:
# continue
# for _ in range(b - 1):
# o = pow(o, 2, i)
# if o == 1: return False
# elif o == i - 1: break
# else: return False
# return True
#
# exit(t())
■ 백준 1929 소수 구하기_실버 3 (에라토스테네스의 체)
# 에라토스테네스의 체
m, n = map(int, input().split())
p_list = [1]*(n+1)
p_list[1] = 0
for i in range(2, int(n**0.5)+1):
if p_list[i]:
for j in range(i*i, n+1, i):
p_list[j] = 0
print("\n".join([f"{i}" for i in range(m, n+1) if p_list[i] == 1]))
■ 백준 13909 창문 닫기_실버 5
# 리스트를 나열해보면 규칙성이 있다. 0100100001...
# 그저 "어라? 0이 2의 배수씩 늘어나네?" 싶어서 이를 규칙으로 적용하여 구현했다.
# 하지만 숲이 아니라 나무를 본 것 뿐이었다.
n = int(input())
jmp = 1
k = 1
while jmp < n:
jmp += 2*k+1
k += 1
print(k-1 if jmp > n else k)
# #고수코드: 알고보니 더한 규칙이 있었고, n이 제곱근의 수일 때 창문은 열려 있다.
# print(int(int(input())**.5))
■ 백준 4948 베르트랑 공준_실버 2
# 최초 구현 했을 때 1580ms가 나와서 뭔가 했다.
# 고수 코드를 보는데 소수 리스트를 구해놓고 거기서 뽑아 쓰기만 하는거 같길래 수정했다.
# 그 결과 132ms
# 고수 분들은 슬라이싱 사용하지 않고 이진탐색으로 슬라이싱 하시더라
import sys
def prime(x):
l = [1] * (x + 1)
l[0] = 0
for i in range(2, int(x ** 0.5) + 1):
if l[i]:
for j in range(i * i, x + 1, i):
l[j] = 0
return l
primeList = prime(123456*2)
while 1:
n = int(sys.stdin.readline())
if n == 0: break
else: print(sum(primeList[n+1:2*n+1]))
■ 백준 17103 골드바흐 파티션_실버 2
# # 최초: 2548ms...
# import sys
# def prime(x):
# p_list = [1] * (x+1)
# p_list[:2] = 0,0
# for i in range(2, int(x**0.5)+1):
# if p_list[i]:
# for j in range(i*i,x+1, i):
# p_list[j] = 0
# return p_list
#
# prime_list = prime(1000000)
# for _ in range(int(input())):
# n = int(sys.stdin.readline())
# cnt = 0
# for i in range(n-2,n//2-1,-1):
# if prime_list[i] and prime_list[n-i]:
# cnt += 1
# print(cnt)
# 수정: 596ms
# 소수로 구성된 배열을 리턴해서 사용, 에라토스테네스의 채로 나머지 소수 확인
import sys
def prime(x):
eratos = [0,0] + [1] * (x+1)
for i in range(2, int(x**0.5)+1):
if eratos[i]:
for j in range(i*i,x+1, i):
eratos[j] = 0
prime = [idx for idx,v in enumerate(eratos) if v]
return eratos, prime
eratos, p_list = prime(1000000)
for _ in range(int(input())):
n = int(sys.stdin.readline())
cnt = 0
for x in p_list:
tmp = n-x
if tmp < x: break
else:
if eratos[tmp]:
cnt += 1
print(cnt)
