1.4 소수 알고리즘

1. 소수 판별법

소수(Prime Number)란?

-> 1과 자기자신 외에는 나누어 떨어지는 정수가 없는 양의 정수

-> 2, 3, 5, 7, 11, 13, ....

 

소수 판별법

-> 소수를 판별하고자 하는 정수 N에 대해

    - 2 ~ N-1까지의 정수로 나누어 보는 방법 -O(N)

    - 2 ~ sqrt(N)까지의 정수로 나누어 보는 방법 - O(N^0.5)

        -> 12 = 2*6 = 3*4 = 4*3 = 6*2

 

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

int is_prime(int n)
{
    int i;
    for (i = 2; i < n; i++){
        if (n%i == 0){
            return false;
        }
}
    return true;
}

 

2. 에라토스테네스의 체

주어진 정수 N보다 작은 모든 소수를 구함(Eratosthenes' sieve)