-
[Python] ๋ฐฑ์ค - 4948 ๋ฒ ๋ฅดํธ๋ ๊ณต์ค__Python/__Algorithm 2022. 1. 7. 17:35
๋ฌธ์
https://www.acmicpc.net/problem/4948
๐น ๋ฌธ์
๋ฒ ๋ฅดํธ๋ ๊ณต์ค์ ์์์ ์์ฐ์ n์ ๋ํ์ฌ, n๋ณด๋ค ํฌ๊ณ , 2n๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์๋ ์ ์ด๋ ํ๋ ์กด์ฌํ๋ค๋ ๋ด์ฉ์ ๋ด๊ณ ์๋ค.
์ด ๋ช ์ ๋ ์กฐ์ ํ ๋ฒ ๋ฅดํธ๋์ด 1845๋ ์ ์ถ์ธกํ๊ณ , ํํ๋ํฐ ์ฒด๋น์ผํ๊ฐ 1850๋ ์ ์ฆ๋ช ํ๋ค.
์๋ฅผ ๋ค์ด, 10๋ณด๋ค ํฌ๊ณ , 20๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์๋ 4๊ฐ๊ฐ ์๋ค. (11, 13, 17, 19) ๋, 14๋ณด๋ค ํฌ๊ณ , 28๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์๋ 3๊ฐ๊ฐ ์๋ค. (17,19, 23)
์์ฐ์ n์ด ์ฃผ์ด์ก์ ๋, n๋ณด๋ค ํฌ๊ณ , 2n๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์์ ๊ฐ์๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
๐น ์ ๋ ฅ
์ ๋ ฅ์ ์ฌ๋ฌ ๊ฐ์ ํ ์คํธ ์ผ์ด์ค๋ก ์ด๋ฃจ์ด์ ธ ์๋ค. ๊ฐ ์ผ์ด์ค๋ n์ ํฌํจํ๋ ํ ์ค๋ก ์ด๋ฃจ์ด์ ธ ์๋ค.
์ ๋ ฅ์ ๋ง์ง๋ง์๋ 0์ด ์ฃผ์ด์ง๋ค.
๐น ์ถ๋ ฅ
๊ฐ ํ ์คํธ ์ผ์ด์ค์ ๋ํด์, n๋ณด๋ค ํฌ๊ณ , 2n๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์์ ๊ฐ์๋ฅผ ์ถ๋ ฅํ๋ค.
ํ์ด ๋ฐฉ๋ฒ
๐น ์ํ
๐น ์์ ํ์
๊ตฌํ ์ฝ๋
import sys def sosu(n): import math for i in range(2,int(math.sqrt(n))+1): if n % i == 0: return False return True inputs = [] while True: n = int(sys.stdin.readline()) if n==0: break inputs.append(n) sosu_chk = [0 for _ in range(2*max(inputs)+1)] for i in range(1,2*max(inputs)+1): if sosu(i): sosu_chk[i] = 1 for num in inputs: print(sum(sosu_chk[num+1:2*num+1]))
์คํ ๊ฒฐ๊ณผ
๐ก
728x90'__Python > __Algorithm' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Python] ๋ฐฑ์ค - 11399 ATM (0) 2022.01.07 [Python] ๋ฐฑ์ค - 11279 ์ต๋ ํ (0) 2022.01.07 [Python] ๋ฐฑ์ค - 11286 ์ ๋๊ฐ ํ (0) 2022.01.07 [Python] ๋ฐฑ์ค - 1927 ์ต์ ํ (0) 2022.01.07 [Python] ๋ฐฑ์ค - 2667 ๋จ์ง๋ฒํธ ๋ถ์ด๊ธฐ (0) 2022.01.07