[백준] 1978번 - 소수 찾기

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class p1978 {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int cnt = 0;
		int rst = 0;
		
		int a = Integer.parseInt(br.readLine());
		int[] ary = new int[a];

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < a; i++) {
			ary[i] = Integer.parseInt(st.nextToken());
		}
		
		for (int i = 0; i < a; i++) {
			cnt = 0;
			for (int j = 2; j < ary[i]; j++) {
				if (ary[i] % j == 0) {
					cnt++;
				}
			}
			if(ary[i] != 1 && cnt == 0) {
				rst++;
			}
		}
		System.out.println(rst);
	}
}

 

간단히 brute force를 이용해서 모듈러 연산이 0인 갯수가 존재하지 않는 수를 찾으면 된다.

 

문제를 해결하고 나서 검색을 해보니 2부터 해당 배열-1 까지 반복을 하지 않고 해당 배열의 수의 제곱근까지만 반복을해도 소수 판별을 가능하다고 하는 수학 결과식을 보아서 코드를 수정하였다. 수정코드는 아래와 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class p1978 {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int cnt = 0;
		int rst = 0;
		
		int a = Integer.parseInt(br.readLine());
		int[] ary = new int[a];

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < a; i++) {
			ary[i] = Integer.parseInt(st.nextToken());
		}
		
		for (int i = 0; i < a; i++) {
			cnt = 0;
			for (int j = 2; j <= Math.sqrt(ary[i]); j++) {
				if (ary[i] % j == 0) {
					cnt++;
				}
			}
			if(ary[i] != 1 && cnt == 0) {
				rst++;
			}
		}
		System.out.println(rst);
	}
}

 

기존 코드에서 inner for문의 반복을 ary[i]까지였던 값을 그 값의 제곱근으로 변경해주었다.