038 거의 소수

첫번째 코드

 

소수 구하기를 위한 에...라토스테네스의 체를 이용하는 코드를 작성하자!! 까지는 잘 작성했는데,

마지막에 거듭제곱에서 더하는 것에서 애를 먹어 책에서 참고했다!!

 

책과 에라토스테네스의 체를 이용하는 과정은 똑같지만

범위 구성에서 생각이 조금 다르다.

 

책은 그냥 모든 숫자에 대해서 진행하였지만,

나는 거듭 제곱이면 최대값에서 2제곱 아래까지만 진행하여 거기서 소수를 구하고

마지막에 소수의 숫자들이 최소값 이상, 최대값 이하인 경우만 구하면 된다고 생각했다.

 

둘다 정답에 도달한다!

 

import sys
import math
input = sys.stdin.readline

n, m = map(int, input().split())
M = int(math.sqrt(m))
A = list(range(M + 1))

A[1] = 0

for i in range(int(math.sqrt(M)) + 1):
    if A[i] == 0:
        continue
    else:
        for j in range(i + i, M + 1, i):
            A[j] = 0

answer = 0

for i in range(len(A)):
    if A[i] != 0:
        tmp = A[i]
        while A[i] <= m/tmp:
            if A[i] >= n/tmp:
                answer += 1
            tmp = A[i] * tmp

print(answer)

 

통과!:)

---

링크

https://github.com/ornni/programmers/tree/main/%EB%B0%B1%EC%A4%80/Gold/1456.%E2%80%85%EA%B1%B0%EC%9D%98%E2%80%85%EC%86%8C%EC%88%98

programmers/백준/Gold/1456. 거의 소수 at main · ornni/programmers