[Algorithm] 소수 구하기 알고리즘 2 (√N 활용)

소수 판별 알고리즘 2 (√N 활용)

알고리즘 목적

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

알고리즘 원리 : √N 이하의 자연수들로 모두 나눠본다

1. N 이 약수 p와 q로 이루어져 p x q = N 을 만족할 때 ( 1 ≤ 𝑝 , 𝑞 ≤ 𝐍 ) 의 부등식을 만족함.
2. 즉, p와 q는 반비례관계 (p가 증가하면 q는 감소)로 p와 q 중 하나는 " 무조건 " 제곱근인 √N보다 작거나 같다
3. √N 이하의 자연수 중에 나누어 떨어지는 수가 있다면, 이는 1 과 N 을 제외한 다른 자연수가 N 의 약수라는 의미로 소수가 아님.
4. √N 이하의 자연수 중에 나누어 떨어지는 수가 없다면, 소수로 판별

* 시간복잡도 (걸리는 시간) : 대략 √N (√N 이하의 자연수들로만 나누기 때문)

 

실제 알고리즘 구현 (Java)

[참고] 제곱근 : Math.sqrt() 필요함. (Math는 내장함수)

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