24강 - 에라토스테네스의 체 [ 실전 알고리즘 강좌(Algorithm Programming Tutorial) #24 ]

[@오서경-u4t]

시험때문에 여러 블로그 뒤져보고있는데 여기가 이해가 직빵이네요 쵝오입니다.

[@송송송송-j5k]

정말 설명 야무지십니다~ 계속 올려주세요 ㅎㅎ

[@정진홍-m6r]

쓸데없는얘긴데,, 숫자를 지워나갈 때 j=i+i, 숫자의 2배부터가 아니라 j=i*i ,숫자의제곱부터 지워나가는게 알고리즘상 효율적일 것 같네욤 예를들어 5의배수 숫자를 삭제할 때 이미 2,3,4의 배수에서 5*5 전까지 5의배수는 다 지웠으니까요

[@김재훈-f2n4m]

그렇게 하면 number가 커졌을 때 int j에서 overflow 생길 수 있어요 long long 으로 바꿔야합니다

[@zlfpxmzl5126]

질문이 있는데요 2부터 10만까지의 숫자 중 소수를 산출해네는 프로그램인데 int형 데이터 배열 변수 a에 100001개를 넣어주는 이유는 왜 그런가요?

[@dongbinna]

기본적인 배열 선언 관행같은 거라고 보시면 됩니다! 코딩을 할 때 인덱스 자체로 접근할 때도 생길 건데, 그 때 사소한 인덱스 범위를 계산하는 정신적인 소모 비용이 적어진다는 장점이 있어요.

[@이석환-h1u]

2번째 for문으로 소수만 남긴다는게 신기하네영.. j=i+i로 어떻게 소수만 남긴건가요? 이해가 잘 안되네여 ㅠㅠ

[@MrMinbs]

i가 소수이니까 i 다음에 오는 배수는 소수가 아니게 됩니다. 2가 소수이면 2의 배수 4, 6, 8, 10...은 소수가 아니게 되는 거죠. i = 2 = 소수 i + i = 4...6...8...10 들은 소수가 아니게 되는 거에요. 이해하는데 도움이 되셨는지 모르겠네요^^;;;;

[@tv..6531]

말로 언급하는 를 수학공식으로 전환한 다음 내용을 참조하시기 바랍니다. kzbin.info/www/bejne/ena2i2t9ntWonac (알고리즘 작성에도 물론 이용할 수 있습니다.)