[알고리즘] 소수 만들기 시간복잡도 in Java

for(int i=2; i<=LAST_NUM; i++) {
	boolean prime = true;
	for(int j=2; j*j<=i; j++) {
		if(i % j == 0) {
			prime = false;
			break;
		}
	}
	if(prime) System.out.print(i+" ");
}

int[] nums = new int[LAST_NUM+1];
for(int i=2; i<=LAST_NUM; i++) {
	nums[i] = i;					// 각 위치에 숫자를 채워넣고,
}
for(int i=2; i*i<=LAST_NUM; i++) {
	if(nums[i] == 0) continue; 			// 이미 체크된 수의 배수는 확인하지 않음. 
	for(int j = i*i; j<=LAST_NUM; j+=i) 
		nums[j] = 0;				// i를 제외한 i의 배수들은 0으로 체크 
}
for(int i=2; i<=LAST_NUM; i++) {
	if(nums[i] != 0) {
		System.out.print(nums[i]+" ");
  	}	
}

// 비트연산자를 활용한 소수 만들기 
eratosthenes();
// 소수만 출력
for (int i = 0; i <= LAST_NUM; i++) {
	if (isPrime(i)) {
		System.out.print(i + " ");
	}
}

public static char prime[] = new char[(LAST_NUM + 7) / 8 + 1];

public static boolean isPrime(int k) {
  return (prime[k >>> 3] & (1 << (k & 7))) == 0 ? false : true;
}

// 숫자 k가 소수가 아님을 마스킹(해당 비트에 0 설정)
public static void setComposite(int k) {
  prime[k >>> 3] &= ~(1 << (k & 7));
}

public static void eratosthenes() {
  java.util.Arrays.fill(prime, (char) 255); // 모든 비트를 1로 초기화
  setComposite(0); // 0과 1은 소수가 아님
  setComposite(1);
  int i, j;
  for (i = 2; i*i <= LAST_NUM; i++)
    if (isPrime(i))
      for (j = i*i; j <= LAST_NUM; j += i)
        setComposite(j);
}