n보다 작은 소수 출력하기

#include<stdio.h>

int main() {

    int n, x, y;

    printf("n = ");

    scanf("%d", &n);

    // 홀수인 소수를 구하는 변수이다.

    // 3부터 시작하여 2씩 더해간다.

    // 처음에 1을 주는 이유는 while문 안에서 바로 2를 더해주기 때문이다.

    x=1;   

    // 유일한 짝수 소수인 2는 갯수가 1개 이상이면 바로 출력해 준다.

    if(n>0) printf("2 ");

    // 소수가 n-1이 될때 까지 반복한다.

    while(x+2<n) {

        x+=2;  // 2번째 이후 소수는 3부터 시작해서 2씩 증가하면서 따져본다.

        y=3;    // x가 홀수이므로 3부터 2씩 증가하면서 나누어 본다.

        // x가 홀수 이므로 약수가 있다면 홀수인 약수가 있다.

        // 따라서 3부터 시작해서 2씩 더해 가면서 나누어 본다.

        // 만약 약수가 있다면 그 약수의 제곱은 x보다 작아야 한다.

        // 큰 약수는 상대가 되는 작은 약수가 있으므로 3부터 출발해서 나누어 볼때

        // 이미 나누어 보았다고 하겠다. 

        // 따라서 y*y<x 인 경우에만 x를 y가 나누는지 아닌지 테스트해보면 된다.

        // x==y*y라면 x는 소수가 아니다.

        // 따라서 while문을 빠져 나가게 되면 y*y>x일 때만 x는 소수이다.

        while(y*y<x && x%y!=0) { y+=2; }

        if(y*y>x) {  

            printf("%d ", x);

        }

    }

    printf("\n");

    return 0;

}