소수 알고리즘

1. N이 소수인지 판별하는 알고리즘

• N이 소수가 아니라면, a*b (a, b는 2 이상의 자연수)로 나타낼 수 있다
• a가 b보다 작을 때, a는 최대 루트 N, b는 최소 루트 N으로 표시할 수 있다
• 따라서 최대 루트 N까지 나머지 연산을 검사하면 소수인지 아닌지 판별할 수 있다.

https://github.com/surinoel/algorithm/blob/master/1978.cpp

 

#include <stdio.h>
 
int main(void) {
    int n = 111;
    for (int i = 2; i*i <= n; i++) {
        if (n%i == 0) {
            printf("%d It's not prime\n", i);
            return 0;
        }
    }
    printf("It's prime\n");
    return 0;
}

 

2. N까지 소수를 출력하는 알고리즘

• 에라토스테네스의 체

https://github.com/surinoel/algorithm/blob/master/1929.cpp