문제 번호 1978번 : 소수 찾기 - JAVA [자바]

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

 

1978번: 소수 찾기

 

문제 설명

 

주어진 수가 소수인지 아닌지 확인하는 문제입니다.

 

문제 풀이

 

주어진 수가 소수인지 아닌지 맞추면 된는 아주 간단한 문제입니다.

소수는 1과 자기 자신만으로 나누어 떨어지는 1보다 큰 양의 정수. 입니다.

주어진 수를 1과 자기 자신을 제외한 주어진 수보다 작은 모든 수로 나눠보고 나머지가 0이 있으면 소수가 아니게 됩니다.

위에는 사실 소수를 구하는 공식입니다. 더 깊이 들어가면 사실은

 

 

 

자연수 n이 소수인지 아닌지를 판정하려면, 

인 범위에 있는 모든 소수 p로 n을 나누어 보아, 나누어 떨어지지 않으면 소수이고, 나누어 떨어지면 합성수이다.

가 정확한 공식입니다.

https://terms.naver.com/entry.naver?docId=1113970&cid=40942&categoryId=32206 

소수

 

네이버 지식백과에 잘 나와있습니다.

정답

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		int count = 0;
	
		for(int i = 0; i < n; i++) {
			boolean flag = true;
			int num = sc.nextInt();
			if(num == 1) {
				flag = false;
			}
			else if(num != 2) {
				for(int j=2; j<num; j++) {
					if(num%j == 0) {
						flag = false;
					}
				}
			}
			
			if(flag == true) {
				count++;
			}
		}
		
		System.out.println(count);
    }
}

 

flag로 해당 수가 소수인지 아닌지 0으로 나누어 떨어졌는지 안떨어졌는지 확인하고 0으로 떨어지면 flag값을 false로 바꾸어서 합성수(소수가 아닌수)임을 나타내는 방식으로 구현했습니다. 

1이면 무조건 소수임으로 나눌 필요가 없고 2 역시 무조건 수소여서 나눌필요가 없습니다. 2를 나눌경우 2로 나누어 떨어져서 소수가 아니게 될 수 있으니 조건으로 빼주었습니다.