[백준1978/Java] 소수 찾기

반응형

 

SMALL

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

문제

주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.

입력

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

출력

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

예제 입력 1 복사

4
1 3 5 7

예제 출력 1 복사

3

풀이

🦊 소수 판별법 :   - √ n까지의 수로 나누어 떨어지는지 검사    - 단, 1은 제외 ! !

🦊 Math.sqrt() - 자바에서 제곱근을 구하는 함수 - Math : 수학 관련 기능들을 담은 클래스 - sqrt() : square root, 제곱근을 의미

 

1. 정수 배열을 선언

2. 첫 번째 for문 돌면서 입력받은 정수 배열에 저장

3. if문 사용해서 1 제외 (1은 소수 x)

4. 두 번째 for문 : 2~ √n 을 나눠보며 약수 구하기

    ➡️ j=1일 경우 무조건 arr[i] % 1 == 0이므로 의미 없는 검사를 하게 된다

5. j가 arr[i]의 약수라면?  for문 탈출

6. 소수일 경우 a++

 

코드

import java.util.Scanner;

// Math.sqrt(arr[i])
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int a = 0;
        int[] arr = new int[n];
        int j;
        for (int i = 0; i < arr.length; i++) {
            arr[i] = sc.nextInt();
            if (arr[i] == 1) {
                continue;
            }
            for (j = 2; j <= Math.sqrt(arr[i]); j++) {
                if (arr[i] % j == 0) break;
            }
            if (j > Math.sqrt(arr[i])) a++;


        }
        System.out.println(a);
    }
}