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

https://programmers.co.kr/learn/courses/30/lessons/12921?language=java 

코딩테스트 연습 - 소수 찾기

 

풀이

먼저, 소수인지를 판별하는 IsPrime() 함수를 정의하려고한다.
입력에 들어온 숫자 num이 소수라면 1을 소수가 아니라면 0을 return한다.

첫번째 방법

소수는 1과 자기자신으로만 나누어지는 수를 의미한다.
따라서 2부터 입력받은 숫자 n까지 나눠보고 나머지가 0이 되는 수가 없다면 소수로 정의한다.

 public int isPrime(int num){
      for(int i=2; i<=num;i++){
          if(num%i==0) return 0; //false
       }
       return 1;
  }

두번째 방법

해당 숫자의 절반까지만 확인하는 방법이 있는데, 이 원리는 자기자신을 제외하고 절반을 초과하는 숫자에서 나눴을때 나머지가 0이 되는 숫자가 나올수 없다는 점을 이용한것이다. 
N/2까지의 값을 확인하게되서 시간복잡도는 상수를 제외해 O(N)이다.

 public int isPrime(int num){
      for(int i=2; i/2<=num;i++){
          if(num%i==0) return 0; //false
       }
       return 1;
  }

세번째 방법

해당 숫자의 √N까지 확인하는 방법인데, 이 원리는 약수의 중심을 구하는 방법이다. 
이 방법을 사용하면 √N 이후의 값은 확인할 필요가 없게되고, 시간복잡도가 O(√N)이므로 가장 효율적이다.

예를 들어 15의 약수는 1,3,5,15이고
각 숫자들의 곱이 15가 되는 쌍으로 묶으면 1:15, 3:5
15의 값은 대략 3.xx의 값이 나온다.
즉, 약수들의 곱으로 봤을때 루트를 씌운 값이 중간값이 됨을 알 수 있다.

아래는 세번째 방법포함 전체 풀이 코드이다.

class Solution {
    public int solution(int n) {
        int answer = 0;
        for (int i=2; i<=n; i++){
            if(isPrime(i)==1) answer++;
        }
        return answer;
    }
    public int isPrime(int num){
        for(int i=2; i*i<=num;i++){
            if(num%i==0) return 0; //false
        }
        return 1;
    }
}