[자료구조와 알고리즘] 소수 알고리즘

소수란? What is Prime Number?

• 1과 자기 자신 외에는 나누어 떨어지는 정수가 없는 양의 정수
• 소수 판별법:
  • 정수N에 대해 2~N-1까지 나누어 보는 방법
  • 2~sqrt(N)까지의 정수로 나누어 보는 방법

에라토스테네스의 체

• 주어진 정수 N보다 작은 모든 소수를 구한다 

  

#include <iostream>
#include <cmath>
using namespace std;

int number = 120; // 구하고자 하는 소수의 범위
int primeNum[121];

void primeNumberSieve()
{
    // primeNum 배열 초기화
    for (int i = 2; i <= number; i++)
    {
        primeNum[i] = i;
    }

    for (int i = 2; i <= sqrt(number); i++)
    {
        // primeNum[i] 가 0이면 이미 소수가 아니므로 continue
        if (primeNum[i] == 0)
            continue;
        // i*k (k<i) 까지의 수는 이미 검사했으므로 j는 i*i 부터 검사해준다.
        for (int j = i * i; j <= number; j += i)
            primeNum[j] = 0;
    }

    // 소수 출력
    for (int i = 2; i <= number; i++)
    {
        if (primeNum[i] != 0)
            printf("%d\n", primeNum[i]);
    }
}
int main()
{
    primeNumberSieve();
}