๐ŸŒป JAVA/์•Œ๊ณ ๋ฆฌ์ฆ˜, ์ž๋ฃŒ๊ตฌ์กฐ

์•Œ๊ณ ๋ฆฌ์ฆ˜ - ์—๋ผํ† ์Šคํ…Œ๋„ค์Šค์˜ ์ฒด - ์†Œ์ˆ˜ ํŒ๋ณ„ ์•Œ๊ณ ๋ฆฌ์ฆ˜

2020. 9. 30. 23:48
๋ชฉ์ฐจ
  1. ์†Œ์ˆ˜ ๋ž€?
  2. ์†Œ์ˆ˜๋ฅผ ์ฐพ์•„๋ณด์ž
  3. ์ฝ”๋“œ๋กœ ์˜ฎ๊ฒจ๋ณด์ž
  4. ์†Œ์ˆ˜์ธ์ง€ ํŒ๋ณ„ํ•˜๊ธฐ
๋ฐ˜์‘ํ˜•

์•ˆ๋…•ํ•˜์„ธ์š”, ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์ •๋ฆฌํ•˜๋Š” ํฌ์ŠคํŒ…์ž…๋‹ˆ๋‹ค. ๋‹ค๋ฅธ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์ฐธ๊ณ ํ•˜์‹œ๋ ค๋ฉด ํ•ด๋‹น ์นดํ…Œ๊ณ ๋ฆฌ๋ฅผ ์ด์šฉํ•ด์ฃผ์„ธ์š”. ๐Ÿ˜Š

 

'๐ŸŒป JAVA/์•Œ๊ณ ๋ฆฌ์ฆ˜, ์ž๋ฃŒ๊ตฌ์กฐ' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๊ธ€ ๋ชฉ๋ก

๊ณต๋ถ€ํ•œ ๊ฒƒ๋“ค ์ •๋ฆฌํ•œ ๋‚ด์šฉ์„ ํฌ์ŠคํŒ…ํ•ฉ๋‹ˆ๋‹ค.

iseunghan.tistory.com

 

 

 

์†Œ์ˆ˜ ๋ž€?


 1์„ ์ œ์™ธํ•œ ์ˆ˜๋“ค ์ค‘, ๊ทธ ์ˆ˜์˜ ์•ฝ์ˆ˜๊ฐ€ 1 ๊ณผ ์ž๊ธฐ ์ž์‹ ์œผ๋กœ๋งŒ  ์ด๋ฃจ์–ด์ง„ ์ˆ˜๋ฅผ ๋งํ•œ๋‹ค.
ex) 2, 3, 5, 7, 11, 13 ......

 

์†Œ์ˆ˜๋ฅผ ์ฐพ์•„๋ณด์ž


1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20

์ด ์ค‘์—์„œ ์†Œ์ˆ˜์ธ 2, 3์„ ์ด์šฉํ•ด์„œ 2์™€ 3์˜ ๋ฐฐ์ˆ˜๋“ค์„ ์ฐจ๋ก€๋กœ ๋‹ค ์ง€์›Œ ๋ณด๊ฒ ๋‹ค.

1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20

๊ทธ๋Ÿฌ๋ฉด ๋‚จ๋Š” ์ˆ˜๋Š” ์†Œ์ˆ˜๊ฐ€ ๋œ๋‹ค.  [2, 3, 5, 7, 11, 13, 17, 19 ...] 

 

์ฝ”๋“œ๋กœ ์˜ฎ๊ฒจ๋ณด์ž


// ์†Œ์ˆ˜ ์ฐพ๊ธฐ
int number = 20;
int[] num_arr = new int[number];

// 0๋ถ€ํ„ฐ 20๊นŒ์ง€ ๋ฐฐ์—ด์— ๋„ฃ๋Š” ์ฝ”๋“œ ์ƒ๋žต.

for(int i=2; i <= number; i++){
	if(num_arr[j] == 0) continue;
    
	for(int j=i+i; j <= number; j += i){        
        num_arr[j] = 0;
    }
}

์ผ๋‹จ 2์ค‘ for๋ฌธ์„ ์ด์šฉํ•˜์—ฌ, ๋ฐ”๊นฅ for๋ฌธ์— i๋Š” 2๋ถ€ํ„ฐ ์‹œ์ž‘ํ•˜๊ณ  ์•ˆ์ชฝ for๋ฌธ์— 2์˜ ๋ฐฐ์ˆ˜๋งŒ ์ฐพ์•„์„œ 0์„ ๋„ฃ์–ด์ค€๋‹ค. (๊ทธ๋ ‡๋‹ค๋ฉด ํ•ด๋‹น ์ˆ˜์˜ ํ•ด๋‹นํ•˜๋Š” ๋ฐฐ์—ด์˜ ๊ฐ’์ด 0 ์ด๋ฉด ์†Œ์ˆ˜๊ฐ€ ์•„๋‹Œ ๊ฒƒ์ด๋‹ค.) ๊ทธ๋ ‡๊ฒŒ 2๋ถ€ํ„ฐ 20๊นŒ์ง€ ์ญ‰ ๋ฐ˜๋ณตํ•œ๋‹ค. ์ค‘๋ณต ์ฒดํฌ๋ฅผ ํ”ผํ•˜๊ธฐ ์œ„ํ•ด ๋ฐฐ์—ด์˜ ๊ฐ’์ด ์ด๋ฏธ 0์ธ ๊ฒฝ์šฐ๋Š” ๊ฑด๋„ˆ๋›ฐ๋„๋ก ํ•œ๋‹ค.

 

์ด๊ฒŒ ๋ฐ”๋กœ ์—๋ผํ† ์Šคํ…Œ๋„ค์Šค์˜ ์ฒด ์ด๋‹ค.

 

์†Œ์ˆ˜์ธ์ง€ ํŒ๋ณ„ํ•˜๊ธฐ


// num_arr[i] != 0 ์ด๋ฉด ์†Œ์ˆ˜์ด๋‹ค!
for(int i=2; i< num_arr[i]; i++){
	if(num_arr[i] != 0)
		System.out.println( num_arr[i] + " ");
}

์ด๋ฏธ ๊ตฌํ•ด๋†“์€ ๋ฐฐ์—ด์„ ์ˆœํšŒํ•˜๋ฉด์„œ, num_arr[i] ๊ฐ’์ด 0์ด ์•„๋‹๋•Œ๋งŒ ์ถœ๋ ฅํ•ด์ฃผ๋ฉด ๋œ๋‹ค.

 

 

 

 

+ ๋ฐฐ์—ด ์—†์ด ์†Œ์ˆ˜ ํŒ๋ณ„ํ•˜๋Š” ์ฝ”๋“œ


public Boolean isPrimeNumber(int num) {
        int sqrt = (int)Math.sqrt(num); // ์ œ๊ณฑ๊ทผ๊นŒ์ง€๋งŒ ์ฒดํฌ(์‹œ๊ฐ„๋ณต์žก๋„ ์ค„์ด๊ธฐ)
        for (int i = 2; i <= sqrt; i++) {
            if (num % i == 0) { 
                return false;
            }
        }
        return true;
    }

์‹œ๊ฐ„๋ณต์žก๋„๋ฅผ ์ค„์ด๊ธฐ ์œ„ํ•ด์„œ ์ฃผ์–ด์ง„ ์ˆ˜์˜ ์ œ๊ณฑ๊ทผ ๊นŒ์ง€๋งŒ ์ˆœํšŒ๋ฅผ ํ•˜๋ฉด์„œ, num์„ ํ•œ๋ฒˆ์ด๋ผ๋„ ๋‚˜๋ˆ„์–ด ์ง„๋‹ค๋ฉด ๊ทธ ์ˆ˜๋Š” ์†Œ์ˆ˜๊ฐ€ ์•„๋‹Œ ๊ฒƒ์ด๋‹ค.

๋ฐ˜์‘ํ˜•
์ €์ž‘์žํ‘œ์‹œ (์ƒˆ์ฐฝ์—ด๋ฆผ)
  1. ์†Œ์ˆ˜ ๋ž€?
  2. ์†Œ์ˆ˜๋ฅผ ์ฐพ์•„๋ณด์ž
  3. ์ฝ”๋“œ๋กœ ์˜ฎ๊ฒจ๋ณด์ž
  4. ์†Œ์ˆ˜์ธ์ง€ ํŒ๋ณ„ํ•˜๊ธฐ
'๐ŸŒป JAVA/์•Œ๊ณ ๋ฆฌ์ฆ˜, ์ž๋ฃŒ๊ตฌ์กฐ' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€
  • ์•Œ๊ณ ๋ฆฌ์ฆ˜ - ๋ฐฑํŠธ๋ž˜ํ‚น(Back-Tracking)
  • ์•Œ๊ณ ๋ฆฌ์ฆ˜ - ์žฌ๊ท€ ์•Œ๊ณ ๋ฆฌ์ฆ˜ (feat. Factorial, Fibonacci)
  • ์•Œ๊ณ ๋ฆฌ์ฆ˜ - Merge Sort (๋ถ„ํ•  ์ •๋ณต, ๋ณ‘ํ•ฉ ์ •๋ ฌ)
  • ์•Œ๊ณ ๋ฆฌ์ฆ˜ - Counting Sort (์นด์šดํŒ… ์ •๋ ฌ / ๊ณ„์ˆ˜ ์ •๋ ฌ) ์•Œ๊ณ ๋ฆฌ์ฆ˜
iseunghan
iseunghan
๊พธ์ค€ํ•˜๊ฒŒ ์—ด์‹ฌํžˆ..
iseunghan
iseunghan

๊ณต์ง€์‚ฌํ•ญ

  • ์–ด์ œ๋ณด๋‹ค ๋‚˜์€ ์˜ค๋Š˜์ด ๋˜๊ธฐ ์œ„ํ•ด ๐Ÿ”ฅ
  • ๋ถ„๋ฅ˜ ์ „์ฒด๋ณด๊ธฐ (261)
    • ๐Ÿ’ Spring (14)
      • ๊ฐœ๋… ๋ฐ ์ดํ•ด (2)
      • Spring ํ•ต์‹ฌ ๊ธฐ์ˆ  (24)
      • Spring REST API (8)
      • Spring MVC, DB ์ ‘๊ทผ ๊ธฐ์ˆ  (7)
      • Spring Security (23)
      • Spring in Action (1)
    • ๐ŸŒป JAVA (84)
      • ์ž๋ฐ” ORM ํ‘œ์ค€ JPA ํ”„๋กœ๊ทธ๋ž˜๋ฐ (20)
      • ์•Œ๊ณ ๋ฆฌ์ฆ˜, ์ž๋ฃŒ๊ตฌ์กฐ (13)
      • ๋””์ž์ธ ํŒจํ„ด (7)
      • ์ •๋ฆฌ์ •๋ฆฌ์ •๋ฆฌ (43)
      • JUnit (1)
    • ๐Ÿ”– Snippets (3)
      • Javascript (3)
    • โš™๏ธ Devops (22)
      • โ› Git (11)
      • ๐Ÿณ Docker (6)
      • ๐Ÿง Linux (3)
      • ๐ŸŒˆ Jenkins (1)
      • ๐Ÿ“ฌ Kafka (1)
    • ๐Ÿ’ฌ ETC.. (4)
      • ๐Ÿ’ป macOS (2)
    • ๐ŸŒง๏ธ ORM (2)
      • JPA (2)
    • ๐Ÿ Python (2)
    • ๐Ÿ“š Databases (15)
      • ์˜ค๋ผํด๋กœ ๋ฐฐ์šฐ๋Š” ๋ฐ์ดํ„ฐ๋ฒ ์ด์Šค ๊ฐœ๋ก ๊ณผ ์‹ค์Šต(2ํŒ) (3)
      • RealMySQL 8.0 (8)
    • ๐Ÿ”ฅ Computer Science (5)
      • ๐Ÿ“ก ๋„คํŠธ์›Œํฌ (5)
    • ๐Ÿท๏ธ ํ˜‘์—… (1)
    • ๐Ÿ“œ ์ฝ”๋”ฉํ…Œ์ŠคํŠธ (38)
      • BAEKJOON\์ˆ˜ํ•™ 1, ์ˆ˜ํ•™ 2 (8)
      • BAEKJOON\์žฌ๊ท€ (5)
      • BAEKJOON\๋ธŒ๋ฃจํŠธ ํฌ์Šค (3)
      • BAEKJOON\์ •๋ ฌ (1)
      • BAEKJOON\๋ฐฑํŠธ๋ž˜ํ‚น (5)
      • BAEKJOON\BFS, DFS (6)
      • BAEKJOON\์ด๋ถ„ํƒ์ƒ‰ (1)
      • BAEKJOON\๋‹ค์ด๋‚˜๋ฏน ํ”„๋กœ๊ทธ๋ž˜๋ฐ (9)
      • BAEKJOON\๊ทธ๋ฆฌ๋”” ์•Œ๊ณ ๋ฆฌ์ฆ˜ (0)
    • โœจ ISEUNGHAN (1)

์ธ๊ธฐ ๊ธ€

์ตœ๊ทผ ๊ธ€

์ „์ฒด
์˜ค๋Š˜
์–ด์ œ
๋ฐ˜์‘ํ˜•
hELLO ยท Designed By ์ •์ƒ์šฐ.
iseunghan
์•Œ๊ณ ๋ฆฌ์ฆ˜ - ์—๋ผํ† ์Šคํ…Œ๋„ค์Šค์˜ ์ฒด - ์†Œ์ˆ˜ ํŒ๋ณ„ ์•Œ๊ณ ๋ฆฌ์ฆ˜
์ƒ๋‹จ์œผ๋กœ

ํ‹ฐ์Šคํ† ๋ฆฌํˆด๋ฐ”

๊ฐœ์ธ์ •๋ณด

  • ํ‹ฐ์Šคํ† ๋ฆฌ ํ™ˆ
  • ํฌ๋Ÿผ
  • ๋กœ๊ทธ์ธ

๋‹จ์ถ•ํ‚ค

๋‚ด ๋ธ”๋กœ๊ทธ

๋‚ด ๋ธ”๋กœ๊ทธ - ๊ด€๋ฆฌ์ž ํ™ˆ ์ „ํ™˜
Q
Q
์ƒˆ ๊ธ€ ์“ฐ๊ธฐ
W
W

๋ธ”๋กœ๊ทธ ๊ฒŒ์‹œ๊ธ€

๊ธ€ ์ˆ˜์ • (๊ถŒํ•œ ์žˆ๋Š” ๊ฒฝ์šฐ)
E
E
๋Œ“๊ธ€ ์˜์—ญ์œผ๋กœ ์ด๋™
C
C

๋ชจ๋“  ์˜์—ญ

์ด ํŽ˜์ด์ง€์˜ URL ๋ณต์‚ฌ
S
S
๋งจ ์œ„๋กœ ์ด๋™
T
T
ํ‹ฐ์Šคํ† ๋ฆฌ ํ™ˆ ์ด๋™
H
H
๋‹จ์ถ•ํ‚ค ์•ˆ๋‚ด
Shift + /
โ‡ง + /

* ๋‹จ์ถ•ํ‚ค๋Š” ํ•œ๊ธ€/์˜๋ฌธ ๋Œ€์†Œ๋ฌธ์ž๋กœ ์ด์šฉ ๊ฐ€๋Šฅํ•˜๋ฉฐ, ํ‹ฐ์Šคํ† ๋ฆฌ ๊ธฐ๋ณธ ๋„๋ฉ”์ธ์—์„œ๋งŒ ๋™์ž‘ํ•ฉ๋‹ˆ๋‹ค.