lango

찍먹? 부먹?
난 부먹 개발자.

1 minute read



입출력 예시

Input

4
1 3 5 7

Output
3


문제 풀이

이 문제는 주어진 N개 수중에서 소수의 개수를 구해야 한다.
소수 자체를 찾는건 어느 정도 공부하였으니, 각 N마다 소수인지를 판별하면 된다.

  • 소수는 1과 자기 자신만을 약수로 가지기 때문에, N이 1과 자기 자신으로만 나누어 떨어지면 소수이다.


그렇다면 코드를 작성해보자.

1
2
3
4

int N = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
int[] prime_list = new int[N];
for(int i=0; i<N; i++) prime_list[i] = Integer.parseInt(st.nextToken());

N개의 수를 입력받기 위해 N을 입력받고, 공백을 기준으로 각 N개의 수를 입력받아 int배열에 저장한다.


1
2
3
4
5

int cnt = 0;
for(int i=0; i<prime_list.length; i++) {
    if(isPrime(Integer.parseInt(prime_list[i])) == 2) cnt++;
}
bw.write(cnt+"\n");

그리고 저장한 배열만큼 반복하며 isPrime() 함수를 통해 1과 자신만을 가지니 2가 반환된다면 소수이기에 cnt를 증가시킨다.
위 과정을 반복하며 배열의 각각의 N이 소수인지를 판별한다. 


1
2
3
4
5
6
7
8

public static int isPrime(int num) {
    int count = 0;
    for(int i = 1; i <= num; i++) {
        if(num % i == 0) count += 1;
        if(count >= 3) return count;
    }   
    return count;
}

1과 자기 자신 수로만 나눠 떨어진다면 count를 2가 되고, 소수가 아닌 수는 count가 3이 된다.



작성코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

import java.io.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] prime_list = new int[N];
        for(int i=0; i<N; i++) prime_list[i] = Integer.parseInt(st.nextToken());

        int cnt = 0;
        for(int i=0; i<prime_list.length; i++) {
            if(isPrime(prime_list[i]) == 2) cnt++;
        }
        bw.write(cnt+"\n");
        
        bw.flush();
        bw.close();
        br.close();
    }

    public static int isPrime(int num) {
        int count = 0;
        for(int i = 1; i <= num; i++) {
            if(num % i == 0) count += 1;
            if(count >= 3) return count;
        }   
        return count;
    }

}

회고

  • N이 소수인지를 확인하려면 1과 자기 자신만을 약수로 가지는지 검증하면 된다.

You may also enjoy