백준 알고리즘 1978 문제 풀이 - 소수 찾기

 

N개의 숫자를 입력받아 N개의 숫자중 소수의 갯수를 구하는 문제이다.

이전에 풀었던걸 까먹고 한번 더 풀었다 .......

 

비슷비슷 하지만 두 가지 방법으로 풀어보았다.

 

첫번째

import java.util.Scanner;

public class Main {

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

		Scanner s = new Scanner(System.in);
		
		short N = s.nextShort();
		boolean sosu[] = new boolean[1001];
		short num,cnt=0;
		
		sosu[0] = true;
		sosu[1] = true;
		for(short i=2;i<=500;i++){
			for(short j=2;j*i<=1000;j++){
				sosu[i*j]=true;
			}
		}
		
		for(short i=0;i<N;i++){
			num = s.nextShort();
			if (!sosu[num]) cnt++;
		}
		System.out.println(cnt);
	}
}

소수인지 아닌지 판단하는 boolean 배열을 만들었다. 1000개 이하의 수이기 때문에 크기를 1001로 만들어 주었다.

boolean형 배열을 생성하면 디폴트로 false값이 세팅되어 있다.

0과 1은 소수가 아니므로 true로 만들고,  1000의 절반인 500까지 돌며 배수들은 전부 true로 바꿔주었다.

(약수가 있다는 것은 소수가 아니므로 모두 true)

(500까지 도는 이유는 i*j (500*2)는 1000이므로 더 돌릴 필요가 없기 때문에 500까지 돌렸다.)

소수들을 미리 구해놓고 N개의 숫자를 입력 받으면서 boolean배열의 입력 받은 숫자 위치가 false라면 cnt를 1씩 증가시켜 입력을 다 받으면 출력을 해주었다.

 

두번째

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		int n = s.nextInt();
		int cnt=0;
		int i,j;
		int arr[] = new int[n];
		
		for(i=0;i<n;i++) {
			arr[i] = s.nextInt();
		}
		for(i=0;i<n;i++) {
			for(j=2;j<=arr[i]/2;j++) {
				if(arr[i]%j == 0) {
					cnt++;
					break;
				}
			}
			if(arr[i]==1)
				cnt++;
		}
		System.out.println(n-cnt);
	}
}

이전에 풀었던 방법이다..

먼저 N개의 수를 입력받고 배열에 담아 둔다.

담아둔 값/2만큼 포문을 돌려 약수가 있으면 cnt를 1씩 증가시키고 다음 포문으로 넘어간다.

n개의 데이터에서 약수가 있는 값만큼 빼주면 소수의 개수가 나온다.