백준(S2) 1929번: 소수 구하기 (c11,c99)

코드를 보기에 앞서, 이 문제를 처음 보는 사람은 "어 뭐야 쉽네??", "이게 왜 실버2??" 이런 생각을 할 수 있다.

그러나 제출을 해보면 100중 95는 시간초과가 될 것 이다.

그런 사람들은 에라토스테네스의 체를 한번 확인해보고 코딩을 해보자

소수는 1과 자기 자신으로만 나눠지는 수다.

그런 특성을 이용해서 120보다 작은 수의 소수를 구할때는 11까지 숫자들의 배수만 제외해도 구해진다.

왜 11인가? (11^2 > 120)이므로 11까지의 배수다.

필자는 이걸 몰라서 반복문을 이용해 전부 곱했다....

 

Full code

#include <stdio.h>
int main()
{
    int a, a1;
    int result[1000001] = { 0, }; // 1부터 1,000,000까지 입력할수 있다
    result[1] = 1;
    scanf("%d %d", &a, &a1);
    for (int i = 2; i <= a1; i++)
    {
        for (int e = 2; e * i <= a1; e++) // 에라토스테네스의 체 참고
        {
            result[e * i] = 1;
        }
    }
    for (int i = a; i <= a1; i++)
    {
        if (result[i] == 0)
            printf("%d\n", i);
    }
    return 0;
}