[Python] ๋ฐฑ์ค€ 2581 - ์†Œ์ˆ˜
ยท
Algorithm
๋ฌธ์ œ ์ž์—ฐ์ˆ˜ M๊ณผ N์ด ์ฃผ์–ด์งˆ ๋•Œ M์ด์ƒ N์ดํ•˜์˜ ์ž์—ฐ์ˆ˜ ์ค‘ ์†Œ์ˆ˜์ธ ๊ฒƒ์„ ๋ชจ๋‘ ๊ณจ๋ผ ์ด๋“ค ์†Œ์ˆ˜์˜ ํ•ฉ๊ณผ ์ตœ์†Ÿ๊ฐ’์„ ์ฐพ๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ์˜ˆ๋ฅผ ๋“ค์–ด M=60, N=100์ธ ๊ฒฝ์šฐ 60์ด์ƒ 100์ดํ•˜์˜ ์ž์—ฐ์ˆ˜ ์ค‘ ์†Œ์ˆ˜๋Š” 61, 67, 71, 73, 79, 83, 89, 97 ์ด 8๊ฐœ๊ฐ€ ์žˆ์œผ๋ฏ€๋กœ, ์ด๋“ค ์†Œ์ˆ˜์˜ ํ•ฉ์€ 620์ด๊ณ , ์ตœ์†Ÿ๊ฐ’์€ 61์ด ๋œ๋‹ค. ์ž…๋ ฅ ์ž…๋ ฅ์˜ ์ฒซ์งธ ์ค„์— M์ด, ๋‘˜์งธ ์ค„์— N์ด ์ฃผ์–ด์ง„๋‹ค. M๊ณผ N์€ 10,000์ดํ•˜์˜ ์ž์—ฐ์ˆ˜์ด๋ฉฐ, M์€ N๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™๋‹ค. ์ถœ๋ ฅ M์ด์ƒ N์ดํ•˜์˜ ์ž์—ฐ์ˆ˜ ์ค‘ ์†Œ์ˆ˜์ธ ๊ฒƒ์„ ๋ชจ๋‘ ์ฐพ์•„ ์ฒซ์งธ ์ค„์— ๊ทธ ํ•ฉ์„, ๋‘˜์งธ ์ค„์— ๊ทธ ์ค‘ ์ตœ์†Ÿ๊ฐ’์„ ์ถœ๋ ฅํ•œ๋‹ค. ๋‹จ, M์ด์ƒ N์ดํ•˜์˜ ์ž์—ฐ์ˆ˜ ์ค‘ ์†Œ์ˆ˜๊ฐ€ ์—†์„ ๊ฒฝ์šฐ๋Š” ์ฒซ์งธ ์ค„์— -1์„ ์ถœ๋ ฅํ•œ๋‹ค. ์ •๋‹ต import math def is_pr..
[Python] ๋ฐฑ์ค€ 1929 - ์†Œ์ˆ˜ ๊ตฌํ•˜๊ธฐ
ยท
Algorithm
๋ฌธ์ œ M์ด์ƒ N์ดํ•˜์˜ ์†Œ์ˆ˜๋ฅผ ๋ชจ๋‘ ์ถœ๋ ฅํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— ์ž์—ฐ์ˆ˜ M๊ณผ N์ด ๋นˆ ์นธ์„ ์‚ฌ์ด์— ๋‘๊ณ  ์ฃผ์–ด์ง„๋‹ค. (1 ≤ M ≤ N ≤ 1,000,000) M์ด์ƒ N์ดํ•˜์˜ ์†Œ์ˆ˜๊ฐ€ ํ•˜๋‚˜ ์ด์ƒ ์žˆ๋Š” ์ž…๋ ฅ๋งŒ ์ฃผ์–ด์ง„๋‹ค. ์ถœ๋ ฅ ํ•œ ์ค„์— ํ•˜๋‚˜์”ฉ, ์ฆ๊ฐ€ํ•˜๋Š” ์ˆœ์„œ๋Œ€๋กœ ์†Œ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค. ์ •๋‹ต import math def is_prime(num): if num