티스토리 뷰

프로그래밍/알고리즘

[자바] 소수 찾기

LunaStratos 2019. 2. 15. 14:46

일반적인 알고리즘

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import java.lang.reflect.Array;
import java.util.*;
 
public class Main {
 
    public static void main(String[] args) {
        int n = 10;
        int answer = 0;
 
        for (int i = 2; i <= n; i++) {
            boolean flag = true;
            for (int j = 2; j < i; j++) {
 
                if (i % j == 0) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                answer++;
            }
        }
 
 
        System.out.println(answer);
 
    }
 
 
}
 
cs


이 방식은 다 찾아봐야 하기 때문에 시간이 걸린다.


좀더 진보적인 방법은 




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
import java.lang.reflect.Array;
import java.util.*;
 
public class Main {
 
    public static void main(String[] args) {
        long start = System.currentTimeMillis(); //시작하는 시점 계산
 
        int n = 100000;
        int answer = 0;
 
        for (int i = 2; i <= n; i++) {
            boolean flag = true;
            for (int j = 2; j*<= i; j++) {
                if (i % 2 == 0) {
                    flag = false;
                    break;
                }else{
 
                    if (i % j == 0) {
                        flag = false;
                        break;
                    }
                }
 
            }
 
            if (flag) {
 
                answer++;
            }
        }
        System.out.println(answer);
        long end = System.currentTimeMillis(); //프로그램이 끝나는 시점 계산
        System.out.println("실행 시간 : " + (end - start) / 1000.0 + "초"); //실행 시간 계산 및 출력
 
    }
 
 
}
 
cs


기존의 방식이 10000을 넣었을때 1초 정도 걸리면, 진보된 방식은 0.016초가 걸린다.

아마 소수를 구하는 방식의 경우 소수결과보단 출력 시간이 짧은 것을 원하는 형태일 것이다. 아마도...

공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
글 보관함