[Algorithm] 소수 구하기 알고리즘 1

소수 판별 알고리즘

알고리즘 목적

1부터 어떠한 수까지 중에 소수인지 아닌지를 판별하는 알고리즘

알고리즘 원리 :  n-1 이하의 모든 수로 나눠본다.

1. n < 2 이하 (0과 1)은 소수가 아니므로 return
2. n == 2 일 때는 소수
3. n 을 2부터 n-1까지 나눈 나머지( n%i )가 존재하지 않으면 소수
   (약수를 1과 자신만을 가지기 때문. 나머지로는 나눠떨어지지 않기 때문)

* 시간복잡도 (걸리는 시간) : 대략 n (n 이하의 모든 수를 검사하기 때문)

 

실제 알고리즘 구현 (Java)

// 소수 판별 메소드 
public static void is_prime(int number) {
 	// 0 과 1 은 소수가 아니다
	if(number < 2) {
		System.out.print("소수가 아닙니다");
		return;
	}
	
	// 2 는 소수다
	if(number == 2) {
		System.out.print("소수입니다");
		return;
	}
	
       
	for(int i = 2; i < number; i++) {
       
		// 소수가 아닐경우
		if(number % i == 0) {
			System.out.print("소수가 아닙니다");
			return;
		}
	}
	// 위 반복문에서 약수를 갖고 있지 않는경우 소수다.
	System.out.print("소수입니다");
	return;
}