Dplex

Dplex.egloos.com

포토로그


시계

통계 위젯 (화이트)

23
43
108272


소수구하기. 2가지 버전. 알고리즘

 
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
public class Main{        
    public static void main(String[] args) {                                                                                                  
        double first = System.currentTimeMillis();
        int max = 1000000;
        exam1(max);
        double second = System.currentTimeMillis();
        exam2(max);
        double third = System.currentTimeMillis();
        System.out.println("exam1의 시간 : " + (second-first));
        System.out.println("exam2의 시간 : " + (third-second));
    }
 
    private static void exam2(int num) { // 6의배수
        int data[] = new int[num];
        int count=2;
        data[0] = 2;
        data[1] = 3;
        int x1, x2;
        boolean flag = false;
        for(int i=6; i<num-1; i+=6)
        {
            x1 = i-1;
            x2 = i+1;
            flag = false;
            for(int j=0; j<count; j++)
            {
                if(x1%data[j]==0)
                {
                    flag = true;
                    break;
                }
                if(data[j]>Math.sqrt(x1))
                    break;
            }
            if(!flag)
            {
                data[count++] = x1;
            }
            flag = false;
            for(int j=0; j<count; j++)
            {
                if(x2%data[j]==0)
                {
                    flag = true;
                    break;
                }
                if(data[j]>Math.sqrt(x2))
                    break;
            }
            if(!flag)
            {
                data[count++] = x2;
            }
        }
        System.out.println("exam2(6의배수) : "+count);
    }
 
    private static void exam1(int num) { // 체
        boolean arr[] = new boolean[num+1];
        int count=1;
        for(int i=3; i<=num; i+=2)
        {
            if(!arr[i])
            {
                count++;
                if(i<=Math.sqrt(num))
                    for(int k=i; k*i<=num && k*i>0; k+=2)
                    {
                        if(!arr[k*i])
                            arr[k*i] = true;
                    }
            }
        }
        System.out.println("exam1(체) : "+count);
    }
} 
 
 

그리고 결과~!


일단 결론부터 말씀드리자면 제가 나름 생각해놓은 알고리즘(exam2)보다 에라토스테니스의 체를 이용한 방식이

훨씬 빠릅니다~~!.

에라토스테네스의 체를 설명드리자면..

1. 먼저 1은 정의상 소수가 아니니까 제외한다. 한 번 체를 친 셈이다. 남은 숫자는 2 이상의 수다. 이 중 가장 작은 수 2는 소수다. 하나 찾아냈다.

2. 방금 찾아낸 소수 2의 배수는 모두 체를 쳐서 거른다. 즉, 짝수를 모두 걸러내 버리고, 홀수 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, … 만 남긴다는 뜻이다. 남은 수 중 가장 작은 수 3은 소수다. 두 번째 소수 3을 찾아냈다.

3. 방금 찾은 소수 3의 배수 역시 모두 거른다. 즉, 3, 6, 9, 12, 15, … 등등을 모두 걸러내 버리자는 뜻이다. (6, 12, 18 등은 이미 걸러냈지만) 그러면 남는 수는 5, 7, 11, 13, 17, 19, 23, 25, 29, … 등이다. 이 중 가장 작은 수 5도 소수다. 세 번째 소수 발견!

4. 방금 찾은 소수 5의 배수도 역시 모두 걸러낸다. 이제 남은 수는 7, 11, 13, 17, 19, 23, 29, … 등이다. 네 번째 소수 7 발견!

5. 방금 찾은 소수 7의 배수도 역시 모두 걸러낸다. 이제 남은 수는 11, 13, 17, 19, 23, 29, 31, … 등이다. 다섯 번째 소수 11 발견!

6. 위와 같은 조작을 반복한다.

네..
에라토스테네스의 체 에서 발췌했습니다.. 전 그걸 코드로 구현한것이구요..

두번째는 제가 에라토스테네스의 체를 알지 못했을때, 나름 머리쓴다고 쓰면서 소수구하는 문제에서 썻던 방법입니다..

설명드리자면.. 먼저 2,3은 소수라는것을 알고 있습니다. 그걸 배열에 저장한후, 2와 3은 소수이므로 그냥 아무런 의심 가지지 않고

2와 3을 곱합니다.. 그럼 6이 됩니다. 6보다 작은 수는 1,2,3,4,5 이렇게 다섯개입니다. 우리가 어떤 6의 배수에서

다섯개의 수 1,2,3,4,5를 더했을 경우 소수가 되는지 판단해본다고 가정을 해보면...

6*x+1 ... 음.. 애매하네요..

6*x+2 ... 6*x가 2의 배수고 거기에 2를 더했으니깐 당연히 2의 배수가 됩니다.. 그러므로 넌 소수가 아닙니다 ㅋㅋ

6*x+3 ... 6*x가 3의 배수고 거기에 3을 더했으니깐 당연히 3의 배수가 됩니다.. 복사붙여넣기 아닙니다 하나하나 쳤습니다 ㅋㅋ

6*x+4 ... 6*x가 2의 배수입니다. 거기에 2를 더합니다. 네 ... 아시겠죠.. 2의 배수입니다...

6*x+5 ... 마찬가지로 애매하네요...

ps) 6의 배수는 당연히 소수가 아니므로.. 6*x+0은 배제하였습니다..

그러므로 반복문에서 6부터 시작하여 6씩 증가하여 6의 배수에 1과 5를 더하여 소수인지 판단하는 알고리즘을 작성해보았습니다.

하나 더 적용한 방식은 소수를 배열에 계속 넣은후에 소수인지 의심되는 수.. 를 배열에 있는 소수로 나눠지는지 체크를 한후

소수라고 판단되면(?) 다시 배열에 넣습니다..

넵 그래요.. 읽느라고 수고하셨어욤 ㅎㅎ

모르는것 있으시면 댓글달아주세요..

친절하게 정성껏 답해드릴게요 호호

덧글

  • RF 2013/05/09 23:09 # 답글

    오 ... 다이나믹 후로그래밍의 일종인것 같네요 ... 토요일 세미나 기대하겠습니다. ㅋㅋㅋ
  • 굿굿 2013/06/05 17:15 # 삭제 답글

    어떤 수를 소수의 곱으로만 나타내는 것을 소인수분해라 하고, 이 소수들을 그 수의 소인수라고 합니다.
    예를 들면 13195의 소인수는 5, 7, 13, 29 입니다.

    600851475143의 소인수 중에서 가장 큰 수를 구하세요.
    ===================================================

    이란 문제를 풀다가 알게 되었는데 알고리즘 훌륭하시네요~ ㅎ
    잘 배우고 갑니다~ ㅎ
  • Dplex 2013/06/06 05:07 #

    그러게요 ㅋㅋ 저도 나름머리쓴다고 6씩 더하면서 했는데;;;

    역시 배열인덱스 크게 잡아놓고 하나씩 없애가는게 훨씬 빠르더라고요..ㅎ
댓글 입력 영역