[C] 백준 | 1929번 코드 - *소수 구하기

>문제

> 핵심

에라토스테네스의 체

>풀이과정

소수 구하기 문제.

이거 어디서 본 것 같은데??

 

백준 1978번 문제

>> sedangdang.tistory.com/18?category=969000

[C] 백준 | 1978번 코드 - 소수찾기

이미 풀어본 문제다!

다만 저 문제는 1000 이하의 소수를 찾는 것이고 이 문제는 백만까지의 소수를 구해야 하는 것이라는 큰 차이가 있다..

 

그래서 이 문제는 넓은 범위에서 소수를 찾을때 유용하게 쓰이는 알고리즘인 <에라토스테네스의 체> 를 이용했다.

위에 저 문제에서 소수찾는 한가지 방법이라고 배우긴 했는데 실제로 코드로 짜보지는 않았다가 이번에 짜보게 됐다.

 

근데 처음에는 연결리스트로 구현해서 처음에 1부터 백만까지 연결했다가 n의 배수가 되는 노드들을 pop하는 구조로 짜려고 했는데 연결하고 순회하는 시간때문에 그런가 시간초과가 나서 그 방법으로는 하지 못했다..

 

그래서 백만칸의 배열을 만들어서 배열의 인덱스와 실제 자연수랑 맞춰놓고 소수이면 0, 소수가 아니면 1 으로 구분하는 알고리즘을 이용해야했다.. 

 

그리고 i가 백만의 제곱근인 10만까지만 도는 이유는 j가 i * i 부터 백만까지 순회하기 때문.

그럼 j 가 왜 i * i 부터 시작하는지?

 

그건 불필요한 반복을 없애기 위해서

i = 5라고 할때,

j = 5부터 백만까지 순회한다고 하면 5 * 2, 5 * 3, 5 * 4 는 이미 체로 걸려졌는데 불필요한 반복을 하게된다.

그런데 j = 5 * 5 = 25부터 백만까지 순회한다면 불필요한 반복 없이 체로 거를 수 있다!!

 

나도 솔직히 다른사람 코드 보고야 알았다. 쩝.

 

>깨달은점

진짜 해도해도 부족하다..

진작에 공부좀 열심히 할걸..

>코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

int num_list[1000002] = { 1, 1,  };

int main()
{
    int  m, n;
    // longlong을 쓰는 이유 -> i*i를 하면 overflow가 발생할 수 있기때문.
    long long i, j;

    scanf("%d %d", &m, &n);

    // 제곱근까지만 돌면 충분함.
    for (i = 2; i <= 100000; i++)
    {
        // 소수가 아니면
        if (num_list[i] == 1)
            continue;
        // 소수인 경우 0
        num_list[i] = 0;

        // i*i 부터 시작하는 이유 -> 불필요한 반복을 최소화하기 위해서. 
        // i = 5일때, j = 5*2, 5*3, 5*4 는 이미 소수가 아님이 밝혀졌으므로 반복할 필요 X
        // ㅓ = 5*5 부터 5의배수인 자연수를 모두 1로 세팅.
        for (j = i * i; j <= 1000000; j = j + i)
        {
            // 소수가 아닌것들은 1
            num_list[j] = 1;
        }
    }

    for (i = m; i <= n; i++)
    {
        if (num_list[i] != 1)
            printf("%lld\n", i);
    }

    return 0;
}