[수학] 소수 판별하기

소수(Prime Number)

• 약수가 1과 자기 자신 밖에 없는 수
• N이 소수가 되려면, 2보다 크거나 같고, N-1보다 작거나 같은 자연수로 나누어 떨어지면 안된다.
• N의 약수 중에서 가장 큰 것은 N/2보다 작거나 같기 때문이다.
• N = a x b로 나타낼 수 있는데, a가 작을수록 b는 크다.
• 가능한 a중에서 가장 작은 값은 2이기 때문에 b는 N/2를 넘지 않는다.

코드

	private static boolean prime(int n) {
		if(n<2) {
			return false;
		}
		for(int i=2; i<=n/2; i++){
			if(n%i == 0) {
				return false;
			}
		}
		return true;
	}

• 약수가 1과 자기 자신 밖에 없는 수
• N이 소수가 되려면, 2보다 크거나 같고, 루트N 보다 작거나 같은 자연수로 나누어 떨어지면 안된다.
• N이 소수가 아니라면, N=a x b로 나타낼 수 있다.(a <= b)
• a>b라면 두 수를 바꿔서 항상 a<=b로 만들 수 있다.
• 두 수 a와 b의 차이가 가장 작은 경우는 루트 N이다.
• 따라서, 루트 N까지만 검사를 해보면 된다.

코드

	private static boolean prime(int n) {
		if(n<2) {
			return false;
		}
		for(int i=2; i*i<=n; i++){ // i <= 루트 n
			if(n%i == 0) {
				return false;
			}
		}
		return true;
	}

백준 알고리즘