[C] 1929: 소수 구하기

사실 이 문제가 Dynamic Programming로 푸는 것은 아니다.

DP는 점화식을 이용하여 i번째까지 구한 것을 저장하고 이것을  i+1번째를 구할 때 이용하는 것이다.

사실 이걸 그대로 사용하고 있지는 않다.

 

다만 DP에 쓰이는 방법 일부를 사용하고 있다.

i번째 수가 소수인지를 각각 구하는 것이 아니라 1부터 탐색을 할때 소수이면

그 수의 배수들을 따로 저장하여 소수인지 확인하면 된다.

즉 Bottom-up 방식으로 생각해서 구현하면 된다.

 

#include <stdio.h>

int dp[1000001];

int main(void)
  {
    int m,n;
    scanf("%d %d",&m,&n);
    
    for(int i=2;i<=n;i++)
      {
        if(dp[i]==0)
        {
          if(i>=m && i<=n)
          {
            printf("%d\n",i);
          }
          
          int tmp=i;
          int tmp_i=i;
          while(tmp<=n)
           {
             dp[tmp]=1;
             tmp+=tmp_i;
           }
        }
        
      }
        
  }