소수 구하기 문제

<문제>

: 백준 1929번 소수 구하기 문제

 

<풀이 및 회고>

이 문제를 보면서 처음 들었던 생각은 소수를 구하는 알고리즘을 생각했다.

근데 들어오는 데이터가 크기 때문에 여러 알고리즘을 비교하면서 필요한 알고리즘을 선택해야 한다고 생각했다.

먼저 데이터를 담은 리스트를 생성한다. => 데이터들 = [11,30,55,100,1000]

그리고 소수를 구하는 알고리즘을 돌아가면서 연산횟수를 각 데이터에 맞는 리스트를 생성한다.

 

1. 가장 비효율적인 알고리즘

for 데이터 in 데이터들:
    for n in range(2, 데이터 + 1):
        for i in range(2,n):
            cnt += 1
            if n % i == 0:
                break
    출력데이터.append(cnt)
    
 # 출력데이터 = [24, 159, 568, 1701, 79723]

2.덜 효율적인 알고리즘

cnt = 0
ptr = 0
prime = [None] * 500
prime[ptr] = 2
ptr += 1
for 데이터 in 데이터들:
    for i in range(3,데이터,2):
        for j in range(1,ptr):
            cnt += 1
            if i % prime[j] == 0:
                break
        else:
            prime[ptr] = i
            ptr += 1
    출력데이터.append(cnt)
print(출력데이터)

#출력데이터 = [4, 49, 178, 506, 600,15152]

3. 가장 효율적인 알고리즘

ptr = 0
prime = [None] * 500
cnt = 0
prime[ptr] = 2
ptr += 1
for 데이터 in 데이터들:
    for n in range(3,N+1,2):
        i = 0
        while prime[i] * prime[i] <= n:
            cnt += 2
            if n % prime[i] == 0:
                break
            i += 1
        else:
            prime[ptr] = n
            ptr += 1
        출력데이터.append(cnt)
        
  #출력데이터 = [8, 60, 186, 510, 600,6824]

여기서 궁금한 점은 2. 와 3.의 알고리즘에서 데이터가 작을때는 2.의 알고리즘이 더 빠르고 데이터가 클때는 3.의 알고리즘이 더 빠르다.

그 이유는 빅오 표기법에서 알 수 있다.

 

여기에서 빨간색 함수( O(nlogn) )과 보라색( O(n) )을 비교하면 그 이유를 알 수 있다.

만나는 교점을 기준으로 그 교점보다 작으면 O(nlogn)이 더 빠르다.

만나는 교점을 기준으로 그 교점보다 크면 O(n)이 더 빠르다.

 

따라서 데이터가 크면 클수록 3.의 알고리즘이 더 빠르다는 것을 알 수 있다.

따라서 위 문제에 가장 적합한 알고리즘은 3.의 알고리즘이라고 볼 수 있다.

그래서 나는 3. 알고리즘을 통해서 위 문제를 해결했다.

 

<답안코드>

M,N = map(int,input().split())
ptr = 0
prime = [None] * N

prime[ptr] = 2
ptr += 1
# for 데이터 in 데이터들:
for n in range(3,N+1,2):
    i = 0
    while prime[i] * prime[i] <= n:
        if n % prime[i] == 0:
            break
        i += 1
    else:
        prime[ptr] = n
        ptr += 1
for i in range(ptr):
    if prime[i] >= M:
        print(prime[i])