20210120_코테공부

단계별풀기 - 기본수학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)

 

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