소수 구하는 사이트 - sosu guhaneun saiteu

2 소수 구하기 알고리즘

소수를 구하는 알고리즘은 약수의 개수로 판단하는 방법과 배수를 지워 가는 방법이 있습니다. 이 두 가지 알고리즘을 살펴보겠습니다.

알고리즘 ①

먼저 약수가 2개인 것으로 소수를 판별하는 방법입니다.

예를 들어 10이 소수인지 판단하려면 10을 1, 2, …, 9, 10으로 각각 나누어 보고 나머지가 0인 개수가 2개이면 소수라고 할 수 있습니다. 즉, 10을 1, 2, …, 9, 10으로 각각 나누고 나머지가 0이 나올 때마다 개수를 1 증가시킵니다. 그리고 최종적으로 개수가 2이면 소수리스트에 저장합니다. 즉, 약수의 개수가 2개이면 소수입니다.

10은 약수의 개수가 4개이므로 소수가 아니라고 판단합니다. 그렇다면 ‘5는 소수인가?’를 판단하려면 1, 2, 3, 4, 5로 나누어 약수의 개수가 2이면 소수라고 판단하면 되겠지요?

신간 소식 구독하기

뉴스레터에 가입하시고 이메일로 신간 소식을 받아 보세요.

Email address

프로젝트 오일러 문제들을 풀다보니 소수에 관련된 문제가 많이 나왔다.

처음 소수 구하는 알고리즘을 생각할 당시, 관련 지식이 미비해(공부한 지 너무 오래돼서) 구현한 알고리즘이 너무 조잡했다. (속도가 너무 느렸다.)

오늘 다시 차근차근 검색해 가며 다시 짜봤다.

가장 기초적인 방법

1은 소수가 아니다.

2부터 자신의 수 이전까지 나눠서 떨어진다면 소수가 아니다. (소수는 1과 자신 외에 나눠지면 안된다.)

예 ) 15가 소수인지 판단하려면

15를 2로 나눠 나머지가 0인지 판단. 아니면 15를 3으로 나눠 나머지가 0인지 판단..소수가 아님

씩으로 판별을 하다보니 큰 숫자 (600851475143)가 나온다면 엄청난 계산을 해야 했다.

def is_prime(number):
    if number == 1:
        return False

    for i in range(2, number):
        if number % i == 0:
            return False

    return True

나눌 때 절반 까지만 나눔

절반 이상의 숫자들은 확인할 필요가 없는 숫자이기 때문이다.

예를 들어 80이라는 숫자가 있다면, 자기자신을 제외하고 절반을 초과하는 숫자로 나눴을 때 나머지가 0이 되는 숫자가 나올 수가 없기 때문이다.

def is_prime2(number):
    if number < 2:
        return False

    if number == 2:
        return True
    
    if number % 2 == 0:
        return False

    for i in range(3, (number // 2) + 1):
        if number % i == 0:
            return False

    return True

루트까지만 확인

약수의 중심을 구하는 방법이다.

예를 들어 80이라는 숫자가 있다면, 약수들이 1, 2, 4, 5, 8, 10, 16, 20, 40, 80 이 된다.

이것은 1 x 80, 2 x 40, 4 x 20, 5 x 16, 8 x 10, 10 x 8, 16 x 5, 20 x 4, 40 x 2, 80 x 1이 되는 것이다.

이것을 보면 8 이후의 약수들은 8까지의 약수들의 역순(반비례)이다. 이는 80의 제곱근과 엇비슷하다. (80의 제곱근 8.94..........)

따라서 그 이후의 숫자들은 판별할 필요가 없다.

def is_prime3(number):
    if number < 2:
        return False

    if number == 2:
        return True
    
    if number % 2 == 0:
        return False

    for i in range(3, int(number ** 0.5) + 1):
        if number % i == 0:
            return False

    return True

참고사이트

소수(Prime Number) 구하기 효율적 알고리즘 :: 코드자몽

Prime Number(소수) 판별법 알고리즘

Python 제곱과 루트 구하기

순환소수를 입력해주세요.

순환부분을 3번 반복해주세요. (마지막 3번반복으로 자동인식)

입력 예시

• 0.333 = 0.3
• 0.123123123 = 0.123
• 0.999 = 0.9
• 0.1252525 = 0.125

분수로 변환하기

핵심은 이것!

• 두개의 등식을 활용하여 변수의 값을 계산할 줄 알기
• 순환마디의 부분이 계속반복됨을 활용하여 10의 배수로 등식 양변 곱하기
  • 등식의 소수점 이하를 순환하는 부분으로 놓는다.
  • 등식을 두개 만들어 계산하기 위해 순환마디를 1개이상 정수부분으로 만들어 계산한다.

    0.3의 계산을 위해, 주로 3.333… - 0.333…, 9x=3 으로 계산하지만, 순환마디 2개를 정수부분으로 만들어서 33.333… - 0.333…, 99x=33 으로도 가능하다. 하지만 불필요한 약분이 추가로 필요하다.

툴 제작과정

툴을 만들게 된 계기에는 `이런 툴 원해요`에 등록되었고, 딱히 어렵다고 판단하진 않아서입니다.

이런 툴 원해요에 원하시는 툴을 설명해주시면, 자체적으로 가치판단하여 제작을 할 수 있습니다.

물론, 산업용 특수목적 계산기등도 가능합니다. (다만, 난이도와 이용자수, 비용등을 고려하여 제작여부는 보장드리지 않습니다.)

한가지 고려했던점은,

학생들이 생각을 안하게 되고. 숙제로만 사용하지 않을까? 때문에 안만드려고 했었는데요.

최근에는 계산기를 잘 만들면, 원리를 이해시키는데 도움이 되지 않을까라는 생각이 들었습니다.

유명 수학/과학 유튜버 3Blue1Brown의 영상을 보시면 아시겠지만.

수학 및 과학적 원리를 시각적으로 표현해 이해를 돕는 영상을 주로 올리고 있습니다.

원리가 시각적으로 보여진다면, 이해와 응용에 도움이 될것으로 판단하였기 때문입니다.

이 툴은 학교나 학원의 선생님의 답안지 작성에도 사용할 수 있습니다.

생성된 결과를 우클릭하여 이미지를 저장하면, 그대로 사용가능한 답안 이미지가 됩니다.

원래 목적과는 다르게 이해에 도움이되는 시각적 효과를 주지 못한 것 같아 약간 아쉽습니다.
좋은 아이디어가 있으시다면, 댓글로 남겨주세요.

이러한 목적으로 제작되는 계산기는 이해 자료가 같이 생성되어야되기 때문에 제작에 시간이 오래걸릴수있으며, 고등학교 수학 문제(공식)만 다뤄도 하나부터 열까지 설명할 그래프 등 자료를 전부 만드려면 한달 넘게도 걸릴수있기 때문에.. 제작이 어려울 수 있습니다.

코드 1 - i(2 ~ N)를 j(2 ~ i)로 나누기

 N을 입력받고 i를 2~N까지 1씩 더한다.

j가 2부터 i에 도달할때까지 1씩 더하면서 i와 나누어 떨어지면 (1과 자기 자신을 제외한 인수가 있으므로) 소수가 아님.

위 연산을 반복해서 0~N 까지 소수의 개수를 하나하나 판단하여 카운팅한다.

각 범위를 계산하며 시간을 측정해본 결과는 아래 표와 같다.

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

int main() {
    int i, j, cnt=0, flag=1;
    unsigned int min, max;

	// 범위 입력
    printf("min : ");
    scanf_s("%d", &min);
    printf("max : ");
    scanf_s("%d", &max);

	// 2보다 작은 최소 범위가 입력되면 2로 고정
    if (min < 2) min = 2;
	
    printf("입력 받은 범위 내의 소수");
    // i가 입력받은 최소 범위부터 최대 범위까지 반복
    for (i = min; i < max; i++) 
    {
        flag = 1; // 현재수가 소수라고 가정하고 시작
        
    	// j는 2부터 현재의 i 전까지 증가
        for (j = 2; j < i; j++) 
        {
        	// i와 j를 나눈 나머지가 존재하면 소수가 아님
            if (i % j == 0) 
            {
                flag = 0; // flag가 0이면 현재 수(i)는 소수가 아님
                break; // 더 이상 j로 나누어 줄 필요가 없으므로 탈출
            }
        }
		
        // 위에서 판단된 결과가 소수이면(0이 아니면)
        if (flag) 
        {
            cnt++; // 개수를 증가시킴 (입력 받은 범위 내의 소수 개수)
            printf("%d\t", i); // 출력
            
            if (cnt % 5 == 0) 
            {
            	printf("\n"); // 5개 단위로 끊음
            }
        }
    }

    printf("\n%d ~ %d 사이의 소수 개수 : %d개\n", min, max, cnt);

    return 0;
}

코드 2 - i (2 ~ N)를 j (2 ~ i / j)로 나누기

현재 수 i가 2의 배수일 경우 i/2 * 2 = i, 3의 배수일 경우 i/3 * 3 = i, 5와 7의 배수일 경우는 i/5 * 5 = i, i/7 * 7 = i 가 성립한다. (4, 6등은 2와 3의 배수이므로 해당 범위에 포함된다.)

위 공식을 일반화시키면 아래와 같고,

i/n * n = i

여기서 i의 소인수는 j와 i/j의 곱셈이므로 j는 i/j보다 클 수 없다는 가설을 적용하여 코드를 작성했다.

(수가 커질수록 더 많은 범위의 계산이 생략되므로 속도가 빨라짐)

아래 표를 보면 코드1의 방식보다 좀 더 개선된 걸 볼 수 있다.

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

void test(int min, int max) 
{
    clock_t start, end;
    float res;
    int i, j, cnt = 0, flag;

    start = clock();
    for (i = min; i < max; i++)
    {
        flag = 1;
		
        // 기존과 달라진 부분, j로 확인 하는 범위를 i와 현재 j의 나눈 몫까지로 줄였음
        for (j = 2; j <= (int)(i / j); j++)
        {
            if (i%j == 0)
            {
                flag = 0;
                break;
            }
        }

        if (flag)
        {
            cnt++;
        }
    }
    end = clock();

    res = (float)(end - start) / CLOCKS_PER_SEC;

    printf("%d~%d : %d개\t%.3fms\n", min, max, cnt, res);
}

int main() {
    int arr[] = {100, 1000, 10000, 100000, 1000000, 10000000, 1000000000};

    for (int i = 0; i < (int)(sizeof(arr) / sizeof(int)); i++)
    {
        test(2, arr[i]);
    }
    return 0;
}

코드 3 - 에라토스테네스의 체

 에라토스테네스의 체를 활용하여 미리 계산된 소수 여부 테이블을 참조하는 방식으로 개수 확인한다.

작은 범위에서는 위의 알고리즘 들과 비슷하거나 느리지만 큰 수의 범위로 가면 훨씬 빠른걸 볼 수 있다.

#include <iostream>

using namespace std;

typedef unsigned long long ll;

/*
* input : int m
* output : 1부터 m까지의 소수 여부를 sizeof(bool) * (m+1)크기의 bool * 형태로 반환한다.
* 사용 시 반환된 bool array에 해당 자연수를 조회하면 소수 여부를 알 수 있다.
*/
bool *Sieve_of_Eratosthenes(ll m) {
    bool* arr = new bool[m + 1];

    memset(arr, 1, sizeof(bool) * (m+1));
    arr[0] = false;
    arr[0] = false;

    for (ll i = 2; i < m + 1; i++) {
        if (arr[i] == true) {
            for (ll j = i * 2; j < m + 1; j += i) {
                arr[j] = false;
            }
        }
    }

    return arr;
}

int main() {
    clock_t start, end;
    ll N, M;
    ll sum=0;

    start = clock();
    cin >> N >> M;
    bool* arr = Sieve_of_Eratosthenes(M);

    for (ll i = N; i <= M; i++) {
        if (arr[i]) {
            sum++;
        }
    }

    end = clock();
    float res = (float)(end - start) / CLOCKS_PER_SEC;
    cout << "" << N << " " << M << " " << sum << ", " << res << "ms" << endl;
    
    return 0;
}

참고

• 계산 범위의 조절로 100만에서 1억으로 향상되었지만 여전히 큰 수를 처리하기엔 어려움
• 에라토스테네스의 체를 활용할 경우 테이블 생성으로 인해 작은 수 범위에서는 더 오래걸리지만,
  큰 수에서는 훨씬 적은 시간이 걸림. (1억에서 100억 단위로 향상됨)
• Openssl을 활용한 더 큰 소수의 활용은 아래 블로그에 있다.

https://nitwit.tistory.com/17

암호학 - 소수 판별

프로그래밍 입문 단계에서 흔히들 과제로 많이 접해보는 문제이다. 특정 수를 입력했을때 이녀석이 소수인지 아닌지 판별하는 알고리즘을 짜보라는 식의 과제. 만약 여러분이라면 어떻게 풀겠

nitwit.tistory.com

왜 1은 소수가 아닌가?

합성수가 뭐야?