[Algorithm] 소수(Prime Number) 구하기

• 소수(Prime Number): 1보다 크고 자기 자신과 1 이외에 어떤 정수로도 나누어떨어지지 않는 정수
• 합성수(Composite Number): 나누어떨어지는 정수가 하나 이상 존재하는 수

해결 1)

• i가 2 또는 3으로 나누어떨어지지 않으면 4, 6으로도 나누어떨어지지 않는다.
• 즉 2부터 n-1까지의 어떤 소수로도 나누어지지 않는다는 조건을 만족하는지 조사하여, 불필요한 나눗셈을 줄일 수 있다.  (7이 소수인지 여부는 7보다 작은 소수 2,5,3으로 나눗셈을 하여 구한다.)

public ArrayList<Integer> getPrimeNumbers(int num) {
  ArrayList<Integer> primeNumbers = new ArrayList<Integer>();

  for(int i = 2; i <= num; i++) {
    int j;
    for(j = 2; j <= i; j++) {
      if(i % j == 0) {
        break;
      }
    }
    
    if(i == j) {
      primeNumbers.add(i);
    }
  }
  return primeNumbers;
}

개선 1)

• n이하의 소수로 n이 나누어지지 않는 경우 n은 소수이다.
• 짝수는 소수가 될 수 없으므로 홀수만 반복문을 돌린다.

public ArrayList<Integer> getPrimeNumbers(int num) {
  ArrayList<Integer> primeNumbers = new ArrayList<Integer>();
  primeNumbers.add(2);

  for(int i = 3; i <= num; i+= 2) { 
    int j;
    for(j = 1; j < primeNumbers.size(); j++) { 
      if(i % primeNumbers.get(j) == 0) {
        break;
      }
    }
    if(primeNumbers.size() == j) {
      primeNumbers.add(i);
    }
  }
  return primeNumbers;
}

개선 2)

• n의 제곱근 이하의 어떤 소수로도 나누어떨어지지 않는다.

public ArrayList<Integer> getPrimeNumbers(int num) {
  ArrayList<Integer> primeNumbers = new ArrayList<Integer>();
  primeNumbers.add(2);
  primeNumbers.add(3); 

  for(int i = 5; i <= num; i+= 2) {
    boolean flag = false;

    for(int j = 1; primeNumbers.get(j) * primeNumbers.get(j) <= i; j++) {
      if(i % primeNumbers.get(j) == 0) {
        flag = true;
        break;
      }
    }

    if(!flag) {
      primeNumbers.add(i);
    }
  }
  return primeNumbers;
}