[소수구하기] 에라토스테네스의 체 알고리즘 -java

알고리즘 문제를 풀다가 소수를 구해야할 일이 생겨서 알아보게되었다.

소수는 1과 자기 자신만의 약수로 가지는 수이다

에라토스테네스의 접근에 따르면,

N이 소수이기 위해 N이 N의 제곱근보다 크지 않은 어떤 소수로도 나누어지지 않아야 한다.

이 이론을 바탕으로 코드를 짜면 다음과 같다.

1000부터 10000까지의 수 중 소수만 남기는 코드이다. pn이라는 Set을 선언해주고 1000부터 9999까지 넣은 후 체에 걸러주었다

 public static void makePN() {
		 for(int i=1000; i<10000; i++)
			 pn.add(i);
         //2부터 100까지 배수 지우기
         for(int i=2; i<=100; i++) {//2부터 10000의 제곱근인 100까지만 체크하면 구할 수 있다.
       	  for(int j=1000/i; i*j<=10000; j++) {
       		  if(pn.contains(i*j))
       			  pn.remove(i*j);
       	  }        		  
    }
}

1무작정 2중 포문으로 1부터 N까지 곱해서 거르는 것보다는 훨씬 효율적일 것이다.