초이의 끄적끄적

단계별풀기 - 기본수학2

# 9020 골드바흐의 추측 (실버1)

• 짝수를 두 소수의 합으로 나타내는 표현을 그 수의 골드바흐 파티션이라고 한다.
• 각 테스트 케이스에 대해서 주어진 n의 골드바흐 파티션을 출력한다. 출력하는 소수는 작은 것부터 먼저 출력하며, 공백으로 구분한다.
• 만약 가능한 n의 골드바흐 파티션이 여러 가지인 경우에는 두 소수의 차이가 가장 작은 것을 출력한다.
• point. 시간초과 에라토스테네스의 체 사용해서 소수 구하기 
  • prime 값이 True면 소수
• point. 두 소수의 차이가 가장 작은것을 출력한다 & 작은 소수부터 출력한다 -> 중간값부터 확인해본다
  • n = 8 이면 4,4 -> 3,5(break) -> 2,6 -> 1,7 순으로 확인
  • n = 10 이면 5,5(break) -> 4,6 -> 3,7 -> 2,8 -> 1,9 순으로 확인한다. 
  • n = 16  이면 8,8, -> 7,9 -> 6,10 -> 5,11(break) -> ...

def isprime(n):
    n += 1
    prime = [True] * n  # n개의 [True]가 있는 리스트 생성
    for i in range(2, int(n ** 0.5) + 1):  # n의 제곱근까지만 검사
        if prime[i]:  # prime[i]가 True일때
            for j in range(2 * i, n, i):  # prime 내 i의 배수들을 False로 변환
                prime[j] = False
    return prime

for _ in range(int(input())):
    n = int(input())
    prime_list = isprime(n)
    half = n//2
    for i in range(half, 1, -1):
        if prime_list[i] and prime_list[n-i]:
            print(i, n-i)
            break

단계별풀기 - 기본수학2

# 4948 베르트랑 공준 (실버2)

• 각 테스트 케이스에 대해서, n보다 크고, 2n보다 작거나 같은 소수의 개수를 출력한다.
• point. 시간초과 에라토스테네스의 체 사용해서 소수 구하기

def isprime(m, n):
    count = 0
    prime = [True] * n  # n개의 [True]가 있는 리스트 생성
    for i in range(2, int(n ** 0.5) + 1):  # n의 제곱근까지만 검사
        if prime[i]:  # prime[i]가 True일때
            for j in range(2 * i, n, i):  # prime 내 i의 배수들을 False로 변환
                prime[j] = False

    for i in range(m, n):
        if i > 1 and prime[i] == True:  # 1 이상이면서 남은 소수들을 출력
            count+=1
    return count

while True:
    n = int(input())
    n_count = 0
    if n==0:
        break
    print(isprime(n+1,n*2+1)) # n< <=2n

단계별풀기 - 기본수학2

#2581 소수 (실버4)

• M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다.
• 단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다.
• point. 소수란 2보다 큰 자연수 중에서 1과 자기 

M = int(input())
N = int(input())
prime = []

for i in range(M,N+1):
    cnt = 0
    if i == 1:
        continue
    for j in range(2,i):
        if i%j == 0:
            cnt += 1
    if cnt == 0:
        prime.append(i)

if len(prime) == 0:
    print(-1)
else:
    print(sum(prime), min(prime))

#2581 소인수분해 (실버4)

• N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다. N이 1인 경우 아무것도 출력하지 않는다.

N = int(input())
i = 2
while N != 1: # 분해가 전부 될때까지 반복
    if N % i == 0:
        N = N/i
        print(i)
    else:
        i += 1

# 1929 소수 구하기 (실버2)

• M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오. 
• 한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.
• point. 시간 초과 주의 

시간초과 코드

M, N = map(int,input().split())
for i in range(M,N+1):
    cnt = 0
    if i == 1:
        continue
    for j in range(2,i):
        if i%j == 0:
            cnt += 1
    if cnt == 0:
        print(i)

개선 1 ) 제곱근 사용하여 소수 구하기 (시간 4040ms나옴)

N의 약수는 무조건 sqrt(N) 범위에 존재한다.

만약 N이 12라 할때, 12의 제곱근은 약 3.46이다.
12의 약수는 1, 2, 3, 4, 6, 12 이다.
여기서 1과 12를 제외했을 때 이는 2 * 6, 3 * 4, 4 * 3, 6 * 2의 결과이다.

이들의 관계는 몫이 커지면 나누는 값이 작아지거나 나누는 값이 커지만 몫이 작아지는 반비례 관계이다. 결국 N의 절반(제곱근)까지 향하게 되면 이후 몫과 나누는 값이 반대로 바뀌게만 되는 상황이다.

따라서 N의 제곱근까지 나누어 떨어지는지 여부를 조사하면 더 빠르게 소수판별을 할 수 있다.

def isPrime(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

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

for i in range(M, N+1):
    if isPrime(i):
        print(i)

개선 2 ) 에라토스테네스의 체를 사용하여 소수 구하기 (시간 252ms 나옴)

소수(x)의 배수는 약수로 무조건 x를 포함하게 된다.
따라서 절대 소수의 배수는 소수가 될 수 없다. 이를 이용한 것이 에라토스테네스의 체이다.
누구나 알고있는 가장 작은 소수인 2부터 시작해서, 2의 배수를 다 지웠으면, 지워지지 않은 수 중에서 다음 값인 3의 배수를 지워나가고 이를 계속해서 반복해 나가면 소수만 남게된다.
마치 체에 걸러서 남는 것들만 뽑아내는 방식이라고 생각하면 된다.

m, n = map(int, input().split())

def isprime(m, n):
  n += 1                            # for문 사용을 위한 n += 1
  prime = [True] * n                # n개의 [True]가 있는 리스트 생성
  for i in range(2, int(n**0.5)+1): # n의 제곱근까지만 검사
    if prime[i]:                    # prime[i]가 True일때
      for j in range(2*i, n, i):    # prime 내 i의 배수들을 False로 변환
        prime[j] = False

  for i in range(m, n):
    if i > 1 and prime[i] == True:  # 1 이상이면서 남은 소수들을 출력
      print(i)

isprime(m, n)

※ 참고 : 소수 판별법 알고리즘

단계별풀기 - 기본수학2

#1978 소수찾기 (실버4)

• 주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.
• point. 소수란 2보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로 나누어떨어지지 않는 자연수이다.

n = int(input())
n_list = list(map(int, input().split()))
n_count = 0

for i in n_list:
    count = 0
    if i == 1:
        continue
    for j in range(2,i):
        if i%j == 0:
            count +=1
    if count == 0:
        n_count +=1
print(n_count)