소수 찾기 - 외부 메서드 없이 탐색

많은 답이 있을 것 같은 소수 찾기 문제. 

내가 생각해본 나의 풀이 :

isPrime으로 각 소수를 찾는다( i=2일때부터 root n까지 탐색)하고 n%i == 0이면 false를 반환한다.

이 isPrime으로 n까지 수들 돌면서 소수를 뽑는다.

그러나 훨씬 빠른 방법으로 소수를 찾을 수 있다.

그냥 이렇게 써 놓으면 무슨 말인지 모를 수가 있다.

어떤 수부터 n이라는 수까지 탐색을 하면서

배열을 지워 나가는 것이다

1) i=2일 때

i번째 인덱스를 가지고 있는 친구가 처음으로 내용물이 0인 상태로 발견이 되었다.

그러면 answer를 하나 증가시켜주고, 2의 배수인 친구들을 전부 내용물을 1로 바꿔준다.

이건 for문안의 j=j+i에 설정되어있다.

2) i=4일 때

아까 i=2로 인해 내용물이 1로 변했으므로 지나간다.

 

2중 포문을 돌기 때문에 굉장히 느릴것이라고 생각했지만, 내가 짰던 코드보다 훨씬 빠르다.

특히나 for문 안에 있는 j=j+i 스킬이 굉장히 유용할 것 같다.

하나의 포문 안에 변수를 2개 돌리는 스킬도 좋으니 찾아보자