少数

少数定義

nからnまでの数の中で小数だけを求めます

エラトステネスのふるい

コードで実装

function primeNum(num){
//배열을 만들어 자연수들을 나열해보자
  const arr = [];
  //n만큼의 i를 반복시켜 true 값을 넣자.(현재 true는 자연수의 집합) 
  for(let i = 0; i <= n; i++){
  	arr.push(true);
  }
  //true에서 false를 바꿔주면 수를 없애는 것을 표현할 것이다. 
  //소수가 아닌 수를 찾아 false값을 넣어 줄 것이다. index는 자연수가 되겠다.
  // 먼저 소수의 최소값인 2부터 반복을 하는데 2의 제곱부터 2의 배수, 3의 제곱부터 3의 배수를 하여 검사 시간을 단축시킬 수 있다. 건너뛴 제곱의 수 사이 값은 소수만 남아서 가능하다.
  for(let i = 2; i * i <= n; i++){
  	//그 수가 true이면 검사를 해본다.(소수인지 자연수인지 확인검사)
    if(arr[i]){
       //i의 제곱부터 i의 배수들은 전부 false로 넣는다.
       	for(let j = i*i; j <= n; j += i){
        	arr[j] = false;
        }
       }
  }
  //0과 1이 남았다. 이 두 수는 소수가 아님으로 false로 바꿔주자
  arr.splice(0,2,false, false);
  //true인 값이 소수임으로 true인 값만 찾아 true의 길이를 구하자.
  //result의 값에 true인 값만 filter를 이용하여 넣는다. 
  const result = arr.filter((value) => value === true)
  return result.length; 
}
//함수를 실행한다.
primeNum(100); //100까지의 수 중 소수의 갯수 찾아내기. (index만 출력하면 소수가 나옴 ㅋ)