JS 문제 / 반복문 소수 판별

코플릿 17번 문제

IsPrime 소수 구하기

 

 

 

 

소수란?

1과 자기 자신을 제외하고 나누어 떨어지는 수가 없다.

1은 소수가 아니다.

2는 짝수 중 유일한 소수이다.

 

소수 판별하는 방법은 두가지가 있다.

반복문 사용과 제곱근 활용

 

 

 

 

 

소수 판별 방법 1:  반복문만 사용

---

내가 쓴 답이다.

1은 제외한다.

2부터 num까지 1씩 커지는 i로

num가 나뉘어지면 변수에 1이 더해진다.

변수에 저장된 값이 1이면 소수가 맞고,

1보다 크면(1이 아니면) 소수가 아니다.

 

function isPrime(num) {
// num === 1과 num으로만 나뉘어 떨어지는 수 
//2부터 num까지 1씩 커짐
// num % i ===0 이라면 변수=변수 +1
//if 변수가 1이라면 리턴 트루
// 2이상이면 리턴 펄스

let r = 0;
if(num === 1){
return false;
}

for(let i = 2; i <= num; i++){
if(num%i === 0){
r = r+1;
}
}

if(r === 1){
return true;
}
else{
return false;
}
}

이번에 알게된 팁. 아무리 생각해도 맞는데 틀렸다고 할 땐 그냥 처음부터 다시 쓰기...

 

 

 

 

 

 

 

 

 

 

 

 

소수 판별 방법 2:  제곱근 사용

---

num의 제곱근값 까지만 반복하여 1을 제외하고 나뉘어지는 수가 없다면 소수다.

제곱근값 이후에는 어떤 수로 곱해지고 나뉘어지는지의 여부가 같으니까.

예를 들어 a와 b가 같지 않다면

a*b = num인 경우, b*a = num이다.

그럼, a*b === num 인지 확인하면 b*a === num 도 알 수 있다.

그러니까, num의 제곱근값까지만 소수인지 확인한다면 num까지는 그 결과가 같을 것.

 

근데 이 방법만 쓴다면, 2부터 num까지 확인하는 1번 방법 대비 비교가 반밖에 줄어들지 못한다.

2부터 num의 제곱근까지 확인 하니까.

num가 짝수인 경우 먼저 제외하고, 3부터 제곱근까지 홀수만 확인하면 반복문 실행의 횟수가 더 줄어들 수 있다.

그래서 아래와 같은 순서로 식이 만들어진다.

 

1을 제외한다 (1은 소수가 아니다)
2는 짝수 중 유일한 소수다. 2일 때 true가 리턴된다.
2를 제외한 짝수는 소수가 아니다. num가 2로 나누어지면 false가 리턴된다. num대신 Math.sqrt(num)를 사용해도 된다.
홀수로 나누어지면 소수가 아니다. parseInst(Math.sqrt(num))를 3부터 2씩 늘어나는 i로 나누어 떨어지는지 확인하는 것을 반복한다.
위 과정을 지나 남은 수는 소수이다.

function isPrime(num) {
if(num === 1){
return false;
}

if(num === 2){
return true;
}

if(num%2 === 0){
return false;
}

for(let i = 3; i <= parseInt(Math.sqrt(num)); i+=2){
if(num%i === 0){
return false;
}
}
return true;
}

 

 

 

 

parseInt(Math.sqrt(num))하는 이유

제곱근은 계산하면 소수(정수가 아닌 decimal naumber)가 나온다. 

decimal number는 prime number가 될 수 없다.

소수점 아래 값 떄문에 식에서는 true가 리턴될 수 있기 때문에 제곱근 값을 정수로 바꿔주는 parseInt를 해야한다.

 

 

 

 

Number가 아니고 parseInt를 쓰는 이유

Number는 문자열 전체를 숫자로 변환해주고, parseInt는 정수로 변환해주는 함수이다.

 

 

 

 

 

 

 

 

 

 

그냥 하나씩 비교하면 되지 왜 짝수 비교하고 제곱근 해서 홀수 또 비교하나 했는데

따져보면 2번이 반복문 실행을 훨씬 덜하는 방법이다.

17번 문제 덕분에 많은 걸 얻었다.

야 호