배열로 소수 구하기

안녕하세요 오랫만에 알고리즘란에 글을 쓰는 것 같네요. 오늘 알려드릴 알고리즘은 배열을 이용한 소수 구하기입니다.  궁금하죠?

배열을 이용해서 소수를 구하려면 어떻게 해야할까요? 일단 어디까지 구할건지 결정을 하고, 배열을 선언합니다. 이 때 배열의 값들은 모두 0으로 선언해주어야합니다. 그리고 반복문을 2부터 돌려서 그 배열의 값이 0이면 소수, 다른 수면 소수가 아니게 됩니다.  그리고 소수를 발견했으면 그 소수의 배수들을 모두 1로 바꿔주면 됩니다.  약간 횡설수설한 것 같은데 100까지 있는 소수를 구하면서 정리해보겠습니다.

① 배열 100까지 선언                                                  array[101]

② 배열을 모두 0으로 초기화                                        array[101]={0,} 

③ 반복문                                                                  for ( i = 2 ; i <= 100 ;  i++) 

1. array[i] 이 0이면 출력                                       if ( array[i] == 0) print

2. 소수의 배수를 모두 1로 변환                               for ( j = i ; j<=100 ; j+=i )  array[j] = 1

이해가 가셨나요?  제가 코드로 짜봤습니다.

코드를 읽어보고 이해가 안가시는 부분은 댓글 남겨주시면 알려드리겠습니다.