이거 1부터 n까지 소수 찾는건데 만든 사람 이름이 에라토스테네스임다. ㅇㅇ
일단 크게
1. 1~100까지에서 소수만 찾는다
2. 일반화(임의의 수 n으로)
이렇게 생각해봤음.
순서는(1~100 기준)
1. 1~100까지를 리스트업하고
2. 1을 지운다 이럴거면 그냥 2부터 리스트업하자
3. 2의 배수(n%2==0)를 지운다
4. 3의 배수(n%3==0)를 지운다
5. 5의 배수(n%5==0)를 지운다
6. 7의 배수(n%7==0)를 지운다
7. Profit!
대충 이정도. 일반화 하게 되면 sqrt(n)보다 작은 수(이면서 소수)까지 저 작업을 계속 해야 한다. (1~150이면 11의 배수까지)
여기서 문제가 되는 것이 있다면
1. 중간에 4와 6, 8, 9의 배수는 2, 3의 배수 하면서 없어져서 안 지워도 되는데 그걸 컴퓨터에게 어떻게 설명할지(1~100까지면 2, 3, 5, 7만 지우면 되지만 일반화할 경우 저기에 대한 조건도 추가해줘야 한다)
2. 리스트에서 어떻게 뺄건지(빼는 법 모름)
3. 일반화하게 될 경우 나누기 할 수의 범위(sqrt(n)보다 작은 소수)를 어떻게 해야 할지
이정도겠지만.
Reply