-
1456. [Python]거의 소수Python_알고리즘/Gold V 2024. 4. 14. 20:16
1. 문제
https://www.acmicpc.net/problem/1456
2. 접근 방법
- 시간 제한: 2초
- 메모리 제한: 256MB
- 에라토스테네스의 체
3. 파이썬 코드
# 에라토스 테네스의 체를 end 범위까지 시행 def prime_check(end): prime_list = [False, False] + [True]*end for i in range(2,int(end**.5)+1): if prime_list[i]: for j in range(i*2,end+1,i): prime_list[j] = False return prime_list[:end] start, end = map(int,input().split()) # end 범위를 바꿔주기 위해서 end 값 저장 check_end = end cnt = 0 # 제곱수의 범위까지 end 이내에 있어야기 떄문에 end 의 sqrt를 해준 값에 +1 을 end 범위로 설정 end = int(end**.5)+1 # 에라토스 테네스의 체를 end 의 sqrt 값을 대입 num_list = prime_check(end) # end 까지 반복문 진행 for i in range(end): # 소수인 경우 if num_list[i]: # index 에 i 값 넣은 수 while 문 돌림 index = i while index <= check_end: # N 제곱까지 값을 곱해 나감 index *= i # start 와 check_end 사이 범위인 경우 cnt if start <= index <= check_end: cnt += 1 print(cnt)
4. 문제를 풀고난 후 생각
- 문제를 이해를 잘못해서 처음에는 start 값 보다 큰 값부터 end 값까지 갯수를 체크하는 식으로 구현을 했다가 값이 잘못 나오는 것을 보고 다시 생각했다.
- start 값을 넣는 것은 거의 소수 값이 그것보다 큰지를 판단하는데만 사용하고 처음 소수 ~ end 값 까지 소수를 체크해줘야 했다.
- end 값이 10^14 까지 들어오기 때문에 에라토스테네스의 체를 구할때 최대 10**7 까지만 체크해보면 된다.
- 하지만 end 값에 따라서 에라토스테네스의 체 를 적용 시키는 범위를 좀 더 줄일 수 있을 것 같아서 end 값의 0.5 제곱값을 한 값까지 구할 수 있게 에라토스 테네스의 체를 적용시켰고, 에라토스테네스의 체를 구하는 과정에서도 end의 0.5 제곱값 범위까지만 계산해도 두번째 반복문에서 걸러지기 떄문에 한번 더 줄이는 식으로 문제의 시간을 최대한 줄여봤다.
5. 문제를 푸는데 도움이 되는 지식
- 에라토스테네스의 체
'Python_알고리즘 > Gold V' 카테고리의 다른 글
7569. [Python]토마토 (0) 2024.04.25 7682. [Python]틱택토 (0) 2024.04.17 1916. [Python]최소비용 구하기 (1) 2024.03.05 2023. [Python] 신기한 소수 (1) 2024.02.25 9205. [Python] 맥주 마시면서 걸어가기 (0) 2024.02.18