백준 1929) 소수 구하기 (c)

#include<stdio.h>
int main()
{
	int decimal[1000001] = { 0, }; //소수면 0 아니면 1 
	decimal[0] = 1, decimal[1] = 1; //0 1 은 소수가 아니므로 미리 선언 
	int i = 0;
	int j = 0;
	int M = 0;
	int N = 0;
	for (j = 2; j < 1000001 / j; j++)
	{
		if (decimal[j] == 1) continue; //소수가 아니면 통과 
		for (i = j * j; i < 1000001; i += j)
		{
			if (i % j == 0) decimal[i] = 1;
		}
	}
	scanf("%d %d", &M, &N);
	for (i = M; i <= N; i++)
	{
		if (decimal[i] == 0) printf("%d\n", i);
	}
}
/*
for j가 2일때
  for  i=2*2 i+=2
    4%2 참 decimal[4]=1 --> i에 4 더해져서 i는 6이됨
    6%2 참 decimal[6]=1 --> 2 계속 더하면서 2의 배수 1로 처리 8 10 12 .....

for j가 3일때
  for i=3*3 i+=3
     9%3 참 decimal[9]=1 --? i에 3 더해져서 i는 12가됨
     12%3참 decimal[12]=1 --> 3 계속 더하면서 3의 배수 1로 처리 15 18 21 ....
     
for j가 4일때는 이미 j가 2일 때 소수처리 해줬으므로 continue

for j가 5일때   --> 10 15 20 은 2,3의 배수에서 이미 1로 처리함 
  for i=5*5 i+=5
  	25%5 참 decimal[25]=1 --> i에 5 더해져서 i는 30됨
    30%5 참 decimal[30]=1 --> 5 계속 더하면서 5의 배수 1처리 
    
 j++되가면서 각 숫자 배수들 1로 처리 
     
*/

 

앞 문제들을 참고해서 제출하니까 시간 초과 출력 초과가 계속 나와서 뭐가 문제인지 한창 고민하고 찾아봤는데 

에라토스테네스의 체 라는 공식을 이용하면 소수를 찾아내기 편하다는걸 알았다. 이 공식과 블로그 몇개를 찾아서

다시 짜봤는데  다행히 풀렸다! ! !