드디어 풀렸다 소수구하기! 1929 -C언어

범위가 큰 소수구하기를 풀지못해 전전긍긍하던 과거의 포스터 드디어 문제를 풀었습니다.

사실 본인의 힘 100%으로 이루어낸게 아니고 진짜 최선을 다해 여기까지 줄여봤지만

#include<stdio.h>
int main(){
    int n,m,i;
    scanf("%d %d",&n,&m);
    while(n<=m){
        for(i=2;i<n/2;i++){
            if(n%i==0) break;
        }
        if(n/2==i||n==2|| n==3){ //범위 반갈죽해서 작은 숫자가 범위에 안들어와 따로 예외를 만들었다.
            printf("%d\n",n);
        }
        if(n<3){
            n++;
        }
        else{
            n+=2;
        }
    }
}

여기까지가 나의 최선이었고 어떻게 해야할지 손놓고 있었는데 친구가 문제 아래쪽에 보면 알고리즘 종류가 나오는데 거기에 있는 "에라토스테니스의 체"를 검색해서 풀면 된다고 해서 해봤더니 신세계를 보게 되었다.

에라토스테니스의 체

이분의 글이었는데 이 짧은 코드 안에 어떻게 이리 간편하게 소수를 구할 수 있는건지 엄청 놀랐다.

 

물론 이분의 코드만으로 바로 풀리진 않고 조금의 시행착오가 있었지만 이 코드는 진짜 이후에도 계속 기억해두고 싶어서 블로그에 글을 쓰게 되었다.

 

완성된 코드

#include <stdio.h>
#include <math.h>
int main(void)
{
    int c,b;
    scanf("%d %d",&c ,&b);
    int a[1000001] = {0};
    int i, j;

    for(i = 2; i <= sqrt(b); i++) {    // 최대값의 제곱근까지 반복
        if(a[i] == 0) {        //i가 소수이면
            for(j = 2; i * j <= b; j++) {    // 자신을 제외한 i의 배수 제거
                a[i * j] = 1;
            }
        }
    }
    for(i = c; i <= b; i++) {
        if(a[i] == 0 && i>1)  printf("%d\n", i);
    }
}

여태 시행착오들

백준 1929