[JAVA] 소수 찾기

소수란 1과 자기 자신을 제외하고는 약수가 없는 수이다.

 

소수를 찾는 가장 기초적인 방법은 2~n-1 까지 반복문을 돌리거나, 혹은 2~n/2 까지 반복문을 돌리며 나누어봄으로써 소수를 찾을 수 있겠지만, 당연히 이는 효율적이지 못한 방법이다.

 

하지만 아래의 방법을 사용하면 않고 √n까지 나누면 소수인지 알 수가 있다.

이 방법은 O(√n)의 시간 복잡도를 가진다.

boolean isPrime(int n) 
{
	if(n<2) return false;
	for(int i=2; i*i <= n; i++ ) {
		if(n%i ==0) return false;
	}
	return true;
}

 

 

추가로 소수 열을 찾는 방법은 에라토스테네스의 체 알고리즘을 사용하면 빠르게 구할 수 있다.

int[] Eratosthenes(int n) 
{
	Boolean[] dp = new Boolean[n]; // 소수 여부 배열
   	dp[0] = dp[1] = true; // 0,1은 소수가 아니므로 true
   	List<Integer> prime = new LinkedList<Integer>();
   	for(int i=2; i<n; i++) {
   		if(dp[i]) continue;			//소수가 아니라면 continue
   		prime.add(i);				//소수라면 리스트에 추가
   		for(int j=i*2; j<n; j+=i) dp[j] = true;	//소수의 배수는 소수가 아님
   	}
   	int[] ret = new int[prime.size()];
   	int count = 0;
   	foreach (int num:prime) ret[count++] = num;
   	return ret;
}