프로그래머스 ) 소수 찾기

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

프로그래머스

 

class Solution {
    public int solution(int n) {
				int cnt =1;
		if (n<4) {
			
		}else {
			for (int i = 4; i <= n; i++) {
				for (int j = 2; j <= Math.sqrt(i); j++) {
					if (i % j == 0 ) {
						cnt++;
						break;
					}
				}
			}
		}
		
        return n-cnt;
    }
}

• 자연수 n을 나누어 떨어지게 하는 수는 n의 제곱근 보다 항상 작기 때문에
• Math.sqrt()를 통해 제곱근 까지만 나누어 떨어지는지 확인

 

---

+번외
에라토스테네스의 체

• 친절하게도 소수를 찾는 방법을 고안해 낸 사람이 이미 있다.
• 진짜 친절한건가..?

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

개념은 n의 제곱근 보다 작은 수들의 배수를 걸러내면 된다는 것
하지만 코드로 구현이 간단한지는 또 다른 문제

import java.util.ArrayList;
class Solution {
    public int solution(int n) {
        int answer = 0;
        ArrayList<Integer> list = new ArrayList<Integer>();
        boolean check = false;

        for(int i=2; i<=Math.sqrt(n); i++){
            check = false;
            for(int j = 2; j<i; j++){
                if(i%j==0){
                    check = true;  
                    break;
                }
            }
            if(!check){
                list.add(i);
            }
        }

        for(int i=2; i<=n; i++){
            check = false;
            for(int num : list){
                if(i%num == 0 && !list.contains(i)){
                    check = true;
                    break;
                }
            }
            if(!check){
                answer++;
            }
        }
        
        return answer;
    }
}