✔[프로그래머스]소수 찾기

✔문제설명

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다. (1은 소수가 아닙니다.)

제한 조건

• n은 2이상 1000000이하의 자연수입니다.

입출력 예

n	return
10	4
5	3

입출력 예 설명

입출력 예 #1
1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환

입출력 예 #2
1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3을 반환

---

<My solution>

=>소수는 1과 자기 자신으로만 나누어지는 수다 .

※ 여기서 말하는 나누기란 자연수로 나누었을 때 나머지가 0인 경우를 의미합니다.

즉 , 나누어 떨어지는 값이 2개 미만인 갯수를 ++ 해주면 됨 !

 

이렇게 풀어주었는데 but 시간초과로 에러가 뜬다 ㅠㅠㅠㅠㅠㅠㅠ

<개선코드>

=>Math.sqrt함수 사용하면 num의 제곱근보다 작은 수에서 나눠지는 수가 안나온다면 num의 제곱근보다 큰 수에서도 나눠지는 수가 나올 수 없기 때문에, 굳이 제곱근보다 큰 수까지 반복문을 돌릴 필요가 없다.

(예제)

20이라는 숫자로 예를 들어보겠습니다.

​

20으로 나누어떨어지는 약수는

1, 2, 4, 5, 10, 20

입니다.

​

1과 자기 자신을 제외한

2, 4, 5, 10

을 보면,

​

2는 10과 대칭

4는 5와 대칭됩니다.

​

20 / 2 = 10;

20 / 10 = 2;

​

다시 말해

​

2, 4만 확인하면

굳이 5, 10을 확인하지 않아도

된다는 의미가 됩니다.

.

(참고)

https://developerjun2.tistory.com/127

javascript 소수 확인, 제곱근 범위 나누기법으로 가장 효율적으로 소수 판별

<Other Solution>

=> true를 소수라고 선언해주고 나누었을때 나머지가 0이 되면 ( 소수가 아니면) false로 바꿔주고 종료 하고 나머지가 0 이 아니면 true로 바꿔줌

만약 isPrime이 true 이면 count에 +1 을 해줌 

<Other Solution>

=>에라토스테네스의 체를 활용해 보았는데 개념은 소수의 배수들을 제거해 나가면 결국 소수만 남는 방식이다

arr에 n의 길이 만큼 true를 push 해주면 [true,true,true,.......,true] 가 되는데 여기서 숫자 0과 1은 소수가 아니므로 false 를 지정해준다.

 

숫자2부터 n까지 인덱스를 돌면서 만약 i번재 값이 true 인 경우 배열을 돌고 , 소수는 2,3,5와 같이 시작하므로 소수의 배수는 2*2, 2*3, 2*4 .. 이렇게 계산 되므로 k는 2부터 시작해서 n/소수로 나눈수만큼 돌면서 

(i가 2이고 n이 10인경우 , 10/2 인 5까지만 2*5까지 돌아야 하므로)

arr[i*k] (2*2,2*3,2*4,2*5)인 인덱스들은 모두 false로 바꾸어줍니다.

 

 

👉1,2는 소수가 아니고 ,  2를 제외한 2의 배수는 소수가 아니고

    자기자신을 제외한3,5, 7 의 배수는 소수가 아니다 .