소수 알고리즘

이 블로그의 모든 예제코드는 깃허브에서도 볼 수 있습니다.
    https://github.com/AeroCodeX/

소수(Prime-Number)의 정의

1과 자기 자신만을 약수로 갖는 수.  

소수가 아닌 수를 합성수(composite)라고 한다.

그림에서 보듯이 소수는 1과 자신을 제외한 m x n 형태로 표현할 수 없다.

아래는 인덱스가 1,000,000 이하의 소수 테이블이다.

prime_seq_upto1000000.txt

출처 : OEIS_A000040

소수 판별 알고리즘 개요

정확히는 소수 판별(Prime Testing)이 아닌 소수 생성(Prime Generation)알고리즘이다.

N이 소수인지 알고 싶다면 N까지 소수 테이블을 만들고나서 확인해야 한다.

수학적 의미의 판별(Testing)은 완벽한 결과를 보장할 수 없거나 확률론을 기반으로 하기 때문이다.

아래는 현대에서 주로 쓰이는 소수 생성 알고리즘이다.

Function Information

generate_prime_brute()	전역탐색을 통해 소수 테이블을 생성한다.
generate_prime_brute_improved()	향상된 전역탐색을 통해 소수 테이블을 생성한다.
generate_prime_eratos()	에라토스테네스의 체를 통해 소수 테이블을 생성한다.
generate_prime_eratos_improved()	향상된 에라토스테네스의 체를 통해 소수 테이블을 생성한다.
generate_prime_atkin()	엣킨의 체를 통해 소수 테이블을 생성한다.
sieve(int n, bool* map)	주어진 소수 테이블에서 n의 배수를 지운다.
PRIME_MAX	소수 테이블의 상한선.

RunningTime Statistics (3회 평균값, ms)

up to	1,000,000	10,000,000	100,000,000	1,000,000,000	Time-complexity
generate_prime_brute()	110,307	X	X	X	n squre
generate_prime_brute_improved()	12,426	874,370	X	X
generate_prime_eratos()	27	505	4,916	48,127	n(logn)(loglogn)
generate_prime_eratos_improved()	20	270	2,765	28,909
generate_prime_atkin()	22	254	2,499	28,384	N/log log N

1. 전역탐색

<핵심>

    1.  V보다 작은 모든 수로 나누어 떨어지지 않으면 V는 소수이다.

2. 향상된 전역 탐색

<핵심>

    Composite로 나눠보는 건 의미가 없다는 것을 알아야 한다.

    1.  V보다 작은 모든 소수로 나누어 떨어지지 않으면 V는 소수이다. (캐싱된 소수를 활용한다.)

    2.  중간에 찾은 소수는 버리지 않고 별도의 공간에 캐싱한다. (소수를 다시 찾는데 시간이 걸리기 때문이다.)

3. 에라토스테네스의 체(SoA - Sieve of Eratosthenes)

<핵심>

    1.  V가 소수이면 V의 배수는 Composite이다.

4. 향상된 에라토스테네스의 체(Improved-SoE)

<핵심>

    1.  V가 소수이면 V의 배수는 Composite이다.

    2.  sqrt(n) 까지만 조사하면 된다.

    3.  소수려면 6i±1 형태여야 한다.

        6i     → 2와 3의 배수

        6i+1 → 소수일 가능성 있음.

        6i+2 → 2의 배수

        6i+3 → 3의 배수

        6i+4 → 2의 배수

        6i+5 → 소수일 가능성 있음.

5. 엣킨의 체(SoA - Sieve of Atkin)

<핵심>

    1. 수학적 이론을 기반으로 한다.