소수 찾기 알고리즘

input : n (자연수)

1번 방법

2~n-1 까지 나머지가 0인게 존재하면 소수

2번 방법

2~ n/2 까지 나머지가 0인게 존재하면 소수

3번 방법

약수의 중간 값은 무조건 n의 제곱근 이하이다. 1~n의 제곱근까지 나머지가 0인게 존재하면 소수이다.

에라토스테네스의 체

boolean[] getPrimes(int n){
  boolean[] primes = new boolean[n + 1];
  primes[1] = true;
  
  for(int i = 2 ; i <= n ; ++i){
    if(primes[i]) continue; // 소수가 아닌(true) 수는 넘어가기
    for(int j = i + i ; j <= n ; j += i){ // i를 제외한 i의 배수 모두 체크하기
    	primes[j] = true;
    }
  }
}

2부터 시작하여 소수의 배수들을 모두 걸러낸다.
이렇게 하다보면 => n까지의 모든 소수가 판별되게됨.
O(nloglogn)의 시간복잡도를 가진다.

가능한 모든 숫자 만들기

처음엔 for문으로만 해결하려했음. (DP 말고)
손계산을 우선 해보니

DP가 아닌 for문으로만 구현하기에 무리가있음.(for문을 문자 갯수만큼 만들 수 없으므로)

따라서 재귀로 접근하여 풀었음.

for (let check = 0; check < numbers.length; check++) {
    for (let check1 = 0; check1 < numbers.length; check1++) {
      let indexArray = [];
      let string = "";

      func(check, check1, string, indexArray);
     
    }
  }

function func(time, index, string, indexArray) {
    indexArray.push(index);
    if (time === 0) {
      string += stringArray[index];
     
      array.push(string);
     
    } else {
      string += stringArray[index];

      for (let check = 0; check < numbers.length; check++) {
        if (!indexArray.includes(check)) {
          func(time - 1, check, string, [...indexArray]);

          
        }
      }
    }
  }

• time : 몇자리의 숫자인지
• index : time번째에 넣을 문자의 index번호
• string : 해당 반복에 만들어진 문자열
• indexArray : 중복 방 들어가지 않게
  

참조값이 아닌 값자체를 넘겨주도록 해야함

• 올바른 출력

func(time - 1, check, string, [...indexArray]);

• 올바르지 않은 출력

func(time - 1, check, string,indexArray);

다음과 같이 indexArray를 전달해주게 되면 값이 아닌 변수의 참조를 넘겨버린 셈이라서 그 시점의 indexArray에 접근한다.

string변수는 왜 현재 시점의 string이 아닌 호출 시점의 string에 접근할 수 있는 걸까?

배운점

• 호출 시점과 참조 시점 => 변수 위치를 바꾸어 보면서 이해해보자
• 소수 판별 알고리즘은 알고 있는게 좋을듯 하다.

Reference

• https://jongmin92.github.io/2017/11/05/Algorithm/Concept/prime/