[백준] 1978 : 소수 찾기 JAVA 풀이

소수는 1과 자기자신 외의 약수를 가지지 않는 수이다.

어떤 수 n이 있을 때, n을 1부터 n으로 나누었을 때 나눠떨어지는 수가 단 2개여야 한다는 뜻이다.

따라서 입력될 숫자의 개수인 N을 입력받고

N개만큼의 숫자를 입력받은 뒤에 그 수의 약수가 2개일 때마다 소수의 개수를 증가시켜줬다.

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

public class Main{
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine()); // 입력받을 숫자의 개수를 입력받음
        StringTokenizer st = new StringTokenizer(br.readLine(), " "); // N개의 숫자가 공백으로 나뉘어 입력되므로 스트링토크나이저 사용
        int cnt_prime = 0; // N개의 숫자의 약수를 셀 변수
        for(int i=0;i<N;i++){ // 숫자 N개를 입력받음
            int num = Integer.parseInt(st.nextToken()); // 입력받은 수를 저장
            int cnt_divisor =0; // 약수의 개수를 셀 변수
            for(int j=1;j<=num;j++){
                if(num%j==0) cnt_divisor++; // 1부터 입력받은 수로 나눠가며 나눠떨어질 때마다 약수의 개수를 증가시킴
            }
            if(cnt_divisor==2) cnt_prime++; // 약수의 개수가 2개라면 소수이므로 소수의 개수를 증가시킴
        }
        System.out.print(cnt_prime); // 소수의 개수 출력
        
           }
}

 

아래는 소수인지 판별하는 메서드를 사용해서 푼 코드이다.

 

import java.io.*;
import java.util.*;
public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		int cnt = 0;
		for(int i=0;i<N;i++) {
			int a = Integer.parseInt(st.nextToken());
			if(is_prime(a)) cnt++;
		}
		System.out.println(cnt);
	}
	
	public static boolean is_prime(int n) {
		int cnt = 0;
		if(n==1) return false;
		
		for(int i=2;i<=n;i++) {
			if(n%i==0) cnt++;
			if(cnt==2) return false;
		}
		return true;
	}

}