[javascript / 알고리즘] 소수 판별 알고리즘

---

해당 포스팅은 제가 사용하려고 만든 포스팅이므로 자세한 설명은 생략합니다. 만약 이해가 안될 시 댓글을 남겨주시면 답변드리겠습니다.

 

---

 

소수란, 1과 자기자신을 제외한 다른 수로 나눠지지 않는 수 입니다.

그 예로 11, 71 등이 있습니다.

 

이 소수를 판별하는 알고리즘을 만들어 보겠습니다.

 

---

실행함수

// 소수 판별기
function isPrime(n) {
	// 1이하일 경우엔 소수가 아닙니다.
	if (n <= 1) return false;

	// 2와 3일 경우엔 소수 입니다.
	if (n === 2 || n === 3) return true;

	// 2로 나눴을 때 나머지가 0일 경우엔 소수가 아닙니다.
	// 이 말인 즉슨 짝수는 다 소수가 아닙니다.
	if (n % 2 === 0) return false;

	// 최대 n - 1까지 돌려줍니다.
	let divisor = 3;
	while (n > divisor) {
		// 무엇이라도 0으로 떨어진다면 소수가 아닙니다.
		if (n % divisor === 0) return false;

		// 짝수일 경우를 제외한 홀수일 경우를 판단
		divisor += 2;
	}

	// 모든 조건을 통과했을 경우 소수로 인정받습니다.
	return true;
}

 

사용

console.log(isPrime(71));