백준 - 2581번, 1929번 / 소수

2581번 - 소수

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

2581번: 소수

내가 작성한 코드

M = int(input())
N = int(input())
num = [i for i in range(M, N+1)]
prime = []
if num[0] == 1 : num.remove(1)
i = 2
while i*i <= N:
    if i in num:
        prime.append(i)
        num.remove(i)
    for n in num:
        if n % i == 0:
            num.remove(n)
    i += 1
prime.extend(num)
if prime:
    print(sum(prime))
    print(prime[0])
else:
    print(-1)

M부터 N까지의 수를 num에 넣고, i로 나눠지면 num에서 제거한다.

i와 같은 수가 있을 경우엔 prime에 따로 넣고, num에서 제거되지 않은 수들을 prime에 넣어 소수들의 목록을 완성한다.

prime의 합과, 첫번째 값을 출력한다.

 

 

1929번 - 소수 구하기

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

1929번: 소수 구하기

처음 작성한 코드(시간초과)

M, N = map(int, input().split())
numbers = [i for i in range(M, N+1)]
if numbers[0] == 1: numbers.remove(1)
prime = []
i=2
while i*i <= N:
   if i == numbers[0]:
      prime.append(i)
      numbers.remove(i)
   for num in numbers:
      if num % i == 0:
         numbers.remove(num)
   i += 1
prime.extend(numbers)
for p in prime:
   print(p)

위에서 소수를 구하는 방법과 같은 방법으로 코드를 작성해봤는데 시간초과였다. 첫 번째 문제는 10,000이하의 자연수들이 입력되었고, 두 번째 문제는 1,000,000 이하의 자연수였다. 계산해야할 수들이 많아지면서 제한시간 2초를 넘긴 것 같았다.

 

두번째(시간초과)

import math
M, N = map(int, input().split())
numbers = [ i for i in range(M, N + 1) ]
isPrime = [ True for _ in range(M, N + 1) ]
if numbers[0] == 1:
    numbers.remove(1)
    isPrime[0] = False
i = 2
while i*i <= N:
    if numbers[0] == i: numbers.remove(i)
    for num in numbers:
        if num % i == 0:
            isPrime[num - M] = False
            numbers.remove(num)
    if i >= 3: i += 2
    else: i += 1 
for i, p in enumerate(isPrime):
    if p: print(i + M)

입력받은 숫자 범위에서 따로 다른 list를 만들지 않고 numbers의 길이만큼 True를 가진 isPrime을 만들어 소수가 아니면 해당 인덱스(num-M번째)를 False로 바꿔주는 식으로 소수가 아닌 것들을 체크했다.

시간이 초과돼서 나누는 수(i)가 너무 많아서  3부터는 i+=2로 홀수들로만 나눠서 소수인지 확인했다.

그런데 이렇게 해도 시간초과였다.

 

인터넷에서 다른 사람이 올린 글들을 참고해 다시 작성했다(통과).

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)

isPrime이라는 함수를 만들어 소수이면 True를, 아니면 False를 반환하도록 한다.

isPrime에서는 for문으로 입력받은 수의 제곱근까지 나눠지는지 확인해서 중간에 나눠지면 False, 끝까지 나눠지지 않으면 True를 반환한다.

 

 

나는 위의 방법과 통과된 방법이 계산하는 횟수는 같다고 생각했다.

그런데 위의 2581번을 아래 1929번을 푸는 방법으로 바꿔주니 속도가 큰 차이가 났다.

 

두 알고리즘을 그림으로 나타내봤다.

수가 적을 때는 크게 차이가 나지 않지만 확인해야할 수들의 개수가 많아지면 위의 방법에서는 크기가 큰 list를 여러번 탐색하며 확인해야되서 시간이 많이 걸린 것 같다.(나누는 수인 i가 적다고 해도)

 

같은 방법인데 순서만 다르다고 생각했던것이 큰 차이가 날 수 있다는 것을 깨달았다.