밍의 기록들😉

[수학] 소수 판별하기 본문

자료구조, 알고리즘/기본다지기

[수학] 소수 판별하기

민쓰 2018. 8. 16. 20:31

소수(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;
	}

백준 알고리즘


Comments