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

https://programmers.co.kr/learn/courses/30/lessons/12921

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

//테스트코드

import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.*;

class Quiz1_findPrimeNumberTest {
    Quiz1_findPrimeNumber q;

    @BeforeEach
    void setUp() {
        q = new Quiz1_findPrimeNumber();
    }

    @Test
    void testTen() {
        assertEquals(4, q.solution(10));
    }

    @Test
    void testFive() {
        assertEquals(3, q.solution(5));
    }

    @Test
    void testTwo() {
        assertEquals(1, q.solution(2));
    }

}

//프로덕션 코드

public class Quiz1_findPrimeNumber {
    int answer = 0;

    public int solution(int n) {
        for (int i = 2; i <= n; i++) {
            if (checkPrimNumber(i)) {
                answer++;
            }
        }
        return answer;
    }

    private boolean checkPrimNumber(int i) {
        for (int j = 2; j < i; j++) {
            if(i%j==0){
                return false;
            }

        }
        return true;
    }
}

// 두 케이스 시간초과 실패. 지금은 O(n^2)이라 수가 커지면 속도가 급격하게 느려짐.
// 시간을 어디서 줄일 수 있을까?
// 처음 1~n 까지는 하나씩 확인해야 하니까 무조건 돌아야하고.
// 소수를 더 효율적으로 판단할 수 있는 방법이 있을까?

 

Java program to check if a number is prime or not - GeeksforGeeks

//프로덕션 코드

public class Quiz1_findPrimeNumber {
    int answer = 0;

    public int solution(int n) {
        for (int i = 2; i <= n; i++) {
            if (checkPrimNumber(i)) {
                answer++;
            }
        }
        return answer;
    }

    private boolean checkPrimNumber(int m) {
        if(m==2||m==3){return true;}
        if(m%2==0||m%3==0){return false;}
        for(int i=5; i*i<=m; i+=6){
            if(m%i==0||m%(i+2)==0){
                return false;
            }
        }
        return true;
    }
}

// 성공! 설명을 해보자.
//  n-1 까지 다 나눠보지말고 효율적으로 나눠보자.
// 2, 3로 나눠서 나눠진다면 2,3의 배수들은 확인해 줄 필요가 없다.
// 6개씩 묶어보면,
// 6n -> 2,3의 배수
// 6n+1 -> 확인 필요
// 6n+2 -> 2의 배수
// 6n+3 -> 3의 배수
// 6n+4 -> 2의 배수
// 6n+5 -> 확인 필요
// 5,7 부터 시작해서 이것들의 6의 배수로만 나눠보면 된다.
// 계산 횟수가 1/3로 확 줄었다!
// O(n^2) 은 같지만 그 안에서 계산 횟수를 줄이는 것도 속도에 큰 영향을 주는구나!
// 리팩토링하고 마무리하자.

// 프로덕션 코드
public class Quiz1_findPrimeNumber {
    int answer = 0;
    public int solution(int n) {
        for (int i = 2; i <= n; i++) {
            if (checkPrimNumber(i)) {
                answer++;
            }
        }
        return answer;
    }

    private boolean checkPrimNumber(int m) {
        if(m==2||m==3){return true;}
        if(m%2==0||m%3==0){return false;}
        if (checkOtherCases(m)) return false;
        return true;
    }

    private boolean checkOtherCases(int m) {
        for(int i = 5; i*i<= m; i+=6){
            if(m %i==0|| m %(i+2)==0){
                return true;
            }
        }
        return false;
    }
}