[알고리즘과 자료구조] JAVA - 소수 찾기

문제 설명

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.

(1은 소수가 아닙니다.)

제한 조건

n은 2이상 1000000이하의 자연수입니다.

문제풀이

- 처음 아래와 같이 간단하게 해결하려고.. 풀었으나 실행시간에서 문제가 발생됐다.

두번째 for문에서 i가 j보다 작을때까지.. 반복문을 돌렸는데 이부분에서 시간이 오래걸린 것.

class Solution {
    public int solution(int n) {
        int answer = 0;
        int count = 0;
        
        for ( int i = 2; i <= n; i++){
            
            // 2는 소수
            if( i == 2 ){
                answer++;
                continue;
            }
            
            // 3부터 소수 찾기 시작
            for( int j=2; j < i; j++){
                if ( i % j == 0 ){
                    count++;
                    break;
                }
            }
            
            if( count == 0 ) {
                answer++;
            }
            count = 0;
        }
        
        return answer;
    }
    
}

j 값을 루트값으로 계산해서 다시 코드 작성.

- 실제로 위의 소스도 잘못된 데이터가 나오진 않지만 알고리즘은..... 참으로 복잡한 것..

import java.util.*;
class Solution {
    public int solution(int n) {
        int answer = 0;
        
        for ( int i = 2; i <= n; i++){
            int count = 0;
            
            for( int j=2; Math.pow(j, 2) <= i; j++){ // Math.pow(j, 2) 제곱근 구하기
                if ( i % j == 0 ){
                    count++;
                    break;
                }
            }
            
            if( count == 0 ) {
                answer++;
            }
        }
        
        return answer;
    }
    
}