[백준] 1978 - 소수찾기 JAVA

Solved.ac Class 완전정복 프로젝트

Class : 2 ~ 2 ++

 

 

 

---

 

링크

https://www.acmicpc.net/problem/1978

1978번: 소수 찾기

문제

소수 찾기
시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 80183 38070 31003 48.231%
문제
주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.

입력
첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.

출력
주어진 수들 중 소수의 개수를 출력한다.

 

접근방법

주어진 수가 소수인지 아닌지 판별하고, 그 개수를 출력하는 문제이다. 특정 숫자에 대해 소수인지 아닌지 판별하는 것이 포인트라는 점을 알고 풀이에 들어가자.

풀이

[백준] 1926 - 소수 구하기 JAVA

 이전 영상의 로우 레벨 버전 정도라고 보면 될 것 같다. 위 문제에서 제곱근 방식과 에라스토테네스의 체에 대한 개념과 함께 설명하니, 이번 포스팅에선 개념 설명은 생략한다.(모른다면 보고 오는 게 도움이 될 듯하다.) 그러나 다른 점은 1000 이하의 자연수 일 뿐, 범위 내 모든 소수를 찾는 문제는 아니라는 점이다. 그래서 배열을 만들어 찾는 에라스토 테네스의 체 방법보다는 제곱근 방식을 이용하여, 해답을 구했다.

 

 제곱수를 제외한다면, 모든 약수는 쌍을 이루기 때문에 이 점을 이용하여 제곱근 이하의 숫자만 사용하여 소수를 찾는다. 단, 나 역시도 실수한점이 있었는데, 제곱근 까지는 포함해서 생각을 해야한다. 제곱근 미만으로 반복문을 돌렸을 때, 4와 같은 제곱수 (약수가 1, 2, 4)는 2까지 확인을 안 하기 때문에 결과적으로 소수로 판단될 수 있다.

이 점만 제외하면, 크게 어렵지 않게 풀 것이다.

코드

import java.util.Scanner;
public class Main {

    public static void main(String[] args){
        Main test = new Main();
    }

    public Main(){
        Scanner sc = new Scanner(System.in);
        //입력
        int len = sc.nextInt();
        int datas[] = new int[len];
        for (int i = 0 ; i < len ; i++){
            datas[i] = sc.nextInt();
        }

        //로직
        int result = solution(datas);

        //출력
        System.out.println(result);
    }

    public int solution(int[] datas){
        //소수의 갯수
        int result = 0 ;

        //데이터 원소마다 접근
        for (int data : datas){
            //1은 소수가 아니므로 pass
            if( data ==1){
                continue;
            }

            //약수의 갯수를 체크하는 변수
            int cnt = 0;

            //1부터 해당값의 제곱근까지만 반복문 시행
            for (int i = 1 ; i* i <= data ; i++ ){
                //약수라면
                if( data % i == 0 ){
                        //제곱수 일땐 +1
                    if (i * i == data){
                        cnt+=1;
                    }else{
                        //제곱수가 아닐 땐 +2
                        cnt+=2;
                    }
                }
            }

            //약수가 2인 값만 result에 누적
            if(cnt ==2){
                result+=1;
            }

        }
        return result;
    }
}

 

결과

 처음 제곱근 방식을 적용하고는 찾는데, 시간손해를 엄청 본 것 같다. 정확히 알고, 써야 나와 같은 실수를 하지 않을 것이니, 유념해두자.

 

 

---

포스팅에 문제가 있거나, 설명이 잘못된 부분 지적 환영합니다.

더 나은 퀄리티의 콘텐츠를 제공할 수 있도록 노력하겠습니다.

읽어주셔서 감사합니다.