BOJ 수학 2 (완)

4581 🔵 소수

실버4

아이디어

제곱근 이상은 볼 필요가 없어요. 왜냐면 9의 소수를 찾을거야. 9의 제곱근은 3 이내에서 9를 나눌 수 있다면 그건 소수가 아닌게돼.
12를 보자 12의 제곱근은 3.xx -> 4거든 4이내의 수에서 12를 나눌 수 있잖아? 그럼 그건 소수가 아니야
하나면 더해볼게 36을보자 36의 제곱근은 6 -> 6이내에서 나눌수있으면 그것도 소수가 아니지
7을보자 7의 제곱근은 2.xx -> 2이내에서 나눌 수 없어. 소수야
17의 제곱근 4.xx -> 4 이내에서 나눌수없어 소수야.

코드

import math

def is_prime(n):
    if n!=1:
        for i in range(2,int(math.sqrt(n))+1):
            if n%i==0:
                return False
    else:
        return False
    return True

S = int(input())
E = int(input())

sumV = 0
minV = 999999999
flag=0
for n in range(S,E+1):
    if is_prime(n):
        sumV += n
        minV = min(minV,n)
        flag=1
if flag:
    print(sumV)
    print(minV)
else:
    print(-1)

렙업

레벨업!
빨리 실버찍자

1929 🔵 소수구하기

실버2

아이디어

제곱근 이상은 볼 필요가 없어요. 왜냐면 9의 소수를 찾을거야. 9의 제곱근은 3 이내에서 9를 나눌 수 있다면 그건 소수가 아닌게돼.
12를 보자 12의 제곱근은 3.xx -> 4거든 4이내의 수에서 12를 나눌 수 있잖아? 그럼 그건 소수가 아니야
하나면 더해볼게 36을보자 36의 제곱근은 6 -> 6이내에서 나눌수있으면 그것도 소수가 아니지
7을보자 7의 제곱근은 2.xx -> 2이내에서 나눌 수 없어. 소수야
17의 제곱근 4.xx -> 4 이내에서 나눌수없어 소수야.

코드

import math

M,N = map(int,input().split())

def is_prime(n):
    if n!=1:
        for i in range(2,int(math.sqrt(n))+1):
            if n%i==0:
                return False
    else:
        return False
    return True

for n in range(M,N+1):
    if is_prime(n):
        print(n)

리뷰..

이렇게 푸니까 시가닝 엄청 오래 걸린다.. 그런데 다른 방법이 생각나지 않아..

4948 🔵 베르트랑 공준

실버2

아이디어

제곱근 이상은 볼 필요가 없어요. 왜냐면 9의 소수를 찾을거야. 9의 제곱근은 3 이내에서 9를 나눌 수 있다면 그건 소수가 아닌게돼.
12를 보자 12의 제곱근은 3.xx -> 4거든 4이내의 수에서 12를 나눌 수 있잖아? 그럼 그건 소수가 아니야
하나면 더해볼게 36을보자 36의 제곱근은 6 -> 6이내에서 나눌수있으면 그것도 소수가 아니지
7을보자 7의 제곱근은 2.xx -> 2이내에서 나눌 수 없어. 소수야
17의 제곱근 4.xx -> 4 이내에서 나눌수없어 소수야.

코드

import math

def is_prime(n):
    if n!=1:
        for i in range(2,int(math.sqrt(n))+1):
            if n%i==0:
                return False
    else:
        return False
    return True


def solution():
    N = int(input())
    if N==0:
        return
    else:
        cnt = 0
        for n in range(N+1,2*N+1):
            if is_prime(n): cnt+=1
        print(cnt)
        solution()

solution()

리뷰

이것도 시간이 너무 많이 걸렸다... 다른사람코드를 확인해보자..
->
다른사람들 코드를 보니까
문제의 범위내에서 모든 소수를 찾아놓음으로써 시간을 절약했다. 나도 해봐야겠다 지금
에르테네스의 체 활용
->
엄청 빨라짐

import math

N =123456
primes = [1]*(2*N+1)
primes[0],primes[1] =0,0
for i in range(2,int(math.sqrt(2*N))+1):
    if primes[i]:
        for j in range(2*i,2*N+1,i):
            primes[j]=0

while True:
    M = int(input())
    if M==0:
        break
    print(sum(primes[M+1:2*M+1]))

9020 🔵 골드바흐의 추측

실버1

아이디어

에르테네스의 체를 활용해서 소수 리스트를 만들어 놓고 이거 이용합시다!

코드

T = int(input())
import math
primes = [1]*(10000)
primes[0],primes[1] =0,0
for i in range(2,int(math.sqrt(10000))+1):
    if primes[i]:
        for j in range(2*i,10000,i):
            primes[j]=0

for tc in range(T):
    N = int(input())
    temp = []
    for i,n in enumerate(primes[2:N+1]):
        if n:
            temp.append(i+2)
    result = 999999
    ans = []
    for t in temp:
        if t<=N-t and N-t in temp:
            if result >= N-2*t:
                result = N-2*t
                ans = [t,N-t]
    print('{} {}'.format(ans[0],ans[1]))

리뷰

이것도 시간이 엄청 오래 걸렸어요.. 다른사람들의 코드를 보고 고쳐야하는데, 오늘은 먼가 하기가 싫네요.. 난중에 다시 복습할 때, 그 때 볼래요..

렙업

1085 3009 4153 3053 브론즈 문제 풀고 레벨업해따.. 실버탈출하자!!

1002 🔵 터렛

실버4

아이디어

원과 원의 접점은 최대 2개이다.
-> 두 원의 중심거리 **2 < (r1+r2)**2

원과 원이 겹치면 접점은 무한대이다.
-> 중심거리 ==0 and r1==r2

원과 원이 만나면 점이 1개가 된다 ( 원과 원이 만나는 경우는 바깥에서 만나거나 안에서 만나거나)
-> 두 원의 중심거리 **2 = (r1+r2)**2
-> 두 원의 중심거리 **2 = (r1-r2)**2

두개 안만나면 접점은 0이다. (바깥에서 안만나거나 안에서 안만나거나
-> 두 원의 중심거리 **2 > (r1+r2)**2
-> 두 원의 중심거리 **2 > (r1-r2)**2

코드

T = int(input())
for i in range(T):
    x1, y1, r1, x2, y2, r2 = map(int, input().split())
    dis = (x2 - x1) ** 2 + (y2 - y1) ** 2
    if dis == 0 and r1 == r2:
        print(-1)
    elif dis == (r1 + r2) ** 2 or dis == (r1 - r2) ** 2:
        print(1)
    elif dis > (r1 + r2) ** 2 or dis < (r1 - r2) ** 2:
        print(0)
    elif dis < (r1 + r2) ** 2:
        print(2)