[programmers] ์์ ์ฐพ๊ธฐ - Java
1๋ถํฐ ์
๋ ฅ๋ฐ์ ์ซ์ n ์ฌ์ด์ ์๋ ์์์ ๊ฐ์๋ฅผ ๋ฐํํ๋ ํจ์๋ฅผ ๋ง๋๋ ๋ฌธ์ ๋ก, ์๋ผํ ์คํ
๋ค์ค์ ์ฒด ์๊ณ ๋ฆฌ์ฆ์ ์ฌ์ฉํ์ฌ ํ ์ ์์ต๋๋ค. ์ด ์๊ณ ๋ฆฌ์ฆ์ ํน์ ํ ์ซ์์ ์ ๊ณฑ๊ทผ๊น์ง๋ง ์ฝ์์ ์ฌ๋ถ๋ฅผ ๊ฒ์ฆํ์ฌ ์์๋ฅผ ํ๋ณํฉ๋๋ค.
Mar 24, 2024
์์ ์ฐพ๊ธฐ
๋ฌธ์ ์ค๋ช
1๋ถํฐ ์
๋ ฅ๋ฐ์ ์ซ์ n ์ฌ์ด์ ์๋ ์์์ ๊ฐ์๋ฅผ ๋ฐํํ๋ ํจ์, solution์ ๋ง๋ค์ด ๋ณด์ธ์.
์์๋ 1๊ณผ ์๊ธฐ ์์ ์ผ๋ก๋ง ๋๋์ด์ง๋ ์๋ฅผ ์๋ฏธํฉ๋๋ค.
(1์ ์์๊ฐ ์๋๋๋ค.)
์ ํ ์กฐ๊ฑด
- n์ 2์ด์ 1000000์ดํ์ ์์ฐ์์ ๋๋ค.
์ ์ถ๋ ฅ ์
n | result |
10 | 4 |
5 | 3 |
์ ์ถ๋ ฅ ์ ์ค๋ช
์
์ถ๋ ฅ ์ #1
1๋ถํฐ 10 ์ฌ์ด์ ์์๋ [2,3,5,7] 4๊ฐ๊ฐ ์กด์ฌํ๋ฏ๋ก 4๋ฅผ ๋ฐํ
์
์ถ๋ ฅ ์ #2
1๋ถํฐ 5 ์ฌ์ด์ ์์๋ [2,3,5] 3๊ฐ๊ฐ ์กด์ฌํ๋ฏ๋ก 3๋ฅผ ๋ฐํ
solution.java
class Solution { public int solution(int n) { boolean[] isPrime = new boolean[n + 1]; for (int i = 2; i <= n; i++) { isPrime[i] = true; } for (int i = 2; i * i <= n; i++) { if (isPrime[i]) { for (int j = i * i; j <= n; j += i) { isPrime[j] = false; } } } int count = 0; for (int i = 2; i <= n; i++) { if (isPrime[i]) { count++; } } return count; } }
ํต์ฌ ํค์๋
- ํด๋น ๋ฌธ์ ๋ ์๋ผํ ์คํ ๋ค์ค์ ์ฒด ์๊ณ ๋ฆฌ์ฆ์ ํตํด ํด๊ฒฐํ ์ ์๋ค.
- ์๋ผํ ์คํ ๋ค์ค์ ์ฒด ์๊ณ ๋ฆฌ์ฆ์ ์์๋ฅผ ํ๋ณํ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค.
- ์ด๋ค ์๊ฐ ์์์ธ์ง๋ฅผ ํ์ธ ํ ๋๋, ํน์ ํ ์ซ์์ ์ ๊ณฑ๊ทผ๊น์ง๋ง ์ฝ์์ ์ฌ๋ถ๋ฅผ ๊ฒ์ฆํ๋ฉด ๋๋ค.
- ์ซ์ 2๋ถํฐ ์์ํด์ ๋ชจ๋ ์ซ์๋ฅผ 1์ฉ ์ฆ๊ฐํ๋ฉฐ, ํด๋น ์์ ๋ฐฐ์๋ ์์๊ฐ ๋ ์ ์์์ ํ์ํ๋ค.
- ๊ฒ์ฌํ ์์ ์ ๊ณฑ์ด ๊ฒ์ฌํ ๋ฒ์๋ฅผ ๋์ด์์ง ์๋๋ค๋ฉด, ๋ฐ๋ณต์ ๊ณ์ํ๋ค.
๊ฒฐ๋ก !
ํด๋น ๋ฌธ์ ๋ฅผ ํ๋ฉด์ ์๋ผํ ์คํ
๋ค์ค์ ์ฒด ์๊ณ ๋ฆฌ์ฆ์ ์ดํดํ ์ ์์๋ค.
Share article