소수를 구하는데 고대의 그리스 수학자 에라스토스테네스에 의하여 개발된 에라스토스테네스의 체(sieve of Erastosthenes)라는 알고리즘이 있다. 해당 알고리즘은 정해진 범위안의 소수를 찾아주는 비교적 간단한 알고리즘이다. 해당 알고리즘은 정해진 범위만큼의 배열을 생성 후, 해당 배열의 값이 1이면 소수가 아니고 0이면 소수인 알고리즘이다. 처음에는 모든 배열의 값을 0으로 초기화한다. 즉, 처음에는 모든 수를 소수라고 가정한다. 알고리즘은 가장 작은 소수인 2부터 시작한다. 2의 배수들은 소수가 아니기 때문에, 2의 배수에 해당하는 배열의 원소를 1로 변경한다. 다음은 2에서 1을 더해 3으로 증가시키고, 3의 값은 0이므로, 3의 배수를 찾아 1로 바꾼다. 다음 3 + 1 인 4는 1이기 때문에 바로 다음 숫자로 넘어간다. 이렇게 지정된 범위까지 완료하였을 때, 0 값을 가진 원소는 소수가 된다. 이 알고리즘을 사용하여 2부터 n 사이의 소수를 찾아보시오. (n은 1000 이하 3 이상의 자연수 / 출력은 공백으로 구분하여 출력한다.)

100

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

100

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97