[알고리즘] 과제 5. 2의 홀수제곱수 - 1은 소수일까?

소수 찾기 프로그램

방법

1. n-1까지 구하기 O(n)

n-1 까지 소수를 모두 구하는 다이나믹 프로그래밍으로 알고리즘 짜기

2. 소수 배열을 만들어서 소수 배열만 돌면서 나누어지는지 판단 O(n)

소수 배열을 만드는 데에 O(n) => 메리트 없음

3. 루트 n까지 돌리면서 짝수 제외하기 O(sqrt(n))

조건 추가

1. 몇 개의 소수( 3, 5 )를 가지고 해당 수의 배수이면 뛰어넘기

   3, 5 계산 시 나누어떨어지지 않았으면 해당 수의 배수에도 나누어떨어지지 않음

   구현 시 주의

   1. 해당 수가 3으로 나누어떨어지는지, 5로 나누어떨어지는지를 계산하려면 모듈러 연산을 사용해야하는데 시간이 오래 걸림

   변수 하나씩 지정하고 1씩 더하는 방법으로 구성

   2. 3과 5의 공배수가 나오면 먼저 거치는 3의 if문에서 continue 됨으로 5에 처리를 해주어야한다.

   5를 나타내는 수인 five_num이 5를 넘어가면 1로 초기화

코드

/*
    IS 2^61-1 PRIME NUMBER?
    2.305843e+18
    7초
    2020-03-27
*/

#include <stdio.h>
#include <math.h>
#include <time.h>

int main() {
    time_t start, end;
    start = time(NULL);
    long long n = (long long)(pow(2, 61))-1; // 2의 배수는 아님
    long long s_n = (long long)sqrt(n) + 1;

    // 소수 구하기
    char result =0;
    int three_num = 0;
    int five_num = -1;
    for (int i = 1; i <= (int)(s_n / 2); i++, three_num++, five_num++) { // (루트 n) / 2 까지
        if (three_num == 3) { // 나누는 수가 3의 배수이면
            three_num = 1;
            continue;
        }
        else if (five_num == 5) { // 나누는 수가 5의 배수이면
            five_num = 1;
            continue;
        }
        if (n % (2 * i + 1) == 0) { // 3 ~ (홀수만)
            // 소수가 아님
            result = 1;
            break;
        }
    }

    // 결과 출력
    if (result)
        printf("소수입니다.\n");
    else
        printf("소수가 아닙니다.\n");
    end = time(NULL);
    printf("- 동작시간: %lfms\n", (double)(end - start) * 1000);
}

최종 구현시간 : 7초

컴퓨터 사양

컴퓨터 CPU : Intel(R) Core(TM) i7-7500U CPU @ 2.70Ghz

메모리 : 8GB

+

2의 짝수제곱수 -1 은 왜 소수가 아닐까?

2의 짝수제곱수 -1 은 3의 배수이다. 이를 증명해보자.

1. 첫번째 경우

2의 첫번째 짝수제곱수인 2^2에서 1을 빼면 3이다. 이는 3의 배수이다.

2. k번째 경우

2의 k번째 짝수제곱수인 2^k-1 = 3a(a는 자연수) 라고 가정했을 때,

3. k+2번째 경우

k+2번째 경우가 성립하는지 확인해보자.

2^(k+2)-1 
= 4*(2^k)-1 
= 4*(3a+1)-1
= 12a+4-1
= 12a+3 (3의 배수)

따라서 2의 제곱수 -1 의 형태로 나타난 수는 홀수제곱수만 소수인지 판단하면 된다.