백준 2581 소수

https://www.acmicpc.net/problem/2581

2581번: 소수

문제 접근

M과 N의 범위가 그닥 크지 않아 원래 소수를 구하는 방법(2부터 해당 수 까지 나누어서 소수인지 판별)도 좋은 접근 법이다. 하지만 처음에는 1부터 N까지의 수에서 각 소수의 곱을 통해서 소수인지 아닌지를 판별한 후 소수인 수만 해당 범위에 따로 뽑아 정답을 구할 생각이었다. 이를 통해 시간 복잡도가 많이 줄어들거라 생각했으나 알고리즘이 머리속에서 구현이 덜 되어 시간초과가 발생했다.

M = int(input())
N = int(input())
numbers = [0]*(N+1)
for i in range(2,(N+1)):
  if i == index:
    pass
  for j in range(i,(N+1)):
    index = i*j
    if index < len(numbers):
      numbers[index] = 1

decimal = []
for num in range(M,N+1):
  if numbers[num] == 0:
    decimal.append(num)
if decimal:
  print(sum(decimal))
  print(min(decimal))
else:
  print(-1)

이를 통해 그냥 원래 정석대로 문제를 다시 풀었다. index를 1로 채우는 로직은 다음에 다시 시도하여 풀도록 하겠다. 

문제 풀이

M = int(input())
N = int(input())
decimals = []
for i in range(M,N+1):
  if i == 1:
    pass
  elif i == 2:
    decimals.append(i)
  else:
    for j in range(2,i):
      if i%j == 0:
        break
      elif j == i-1:
        decimals.append(i)
if decimals:
  print(sum(decimals))
  print(min(decimals))
else:
  print(-1)