[JAVA] 백준 1978번 소수 찾기 : 소수

1978번: 소수 찾기

 

 

1. 문제 추상화

 

입력받은 N개의 수 중, 소수가 몇 개인지 출력하시오.

 

2. 제약조건

 

N은 100이하이고 수는 1000이하의 수가 주어진다.

 

3. 알고리즘

 

첫 번째 방법 : 아리스토테스의 체

 

1. 0~1000까지의 boolean 배열을 만든다.

2. 0~1000까지 i를 1씩 증가시켜 각 i의 배수를 true로 저장한다.

3. 반복문이 끝난 후, false로 남아있는 인덱스가 소수이다.

 

두 번째 방법 : 제곱근

 

1. 주어진 수가 5라면 5보다 작은 정수를 5에 나누었을 때 나머지가 0이 아니면 소수이다.

2. 1을 제외하고 2, 3, 4를 5와 나누었을 때, 나머지가 0이 되는 수가 없으므로 5는 소수이다.

3. 그러나 굳이 5보다 작은 정수 모두를 나눌 필요는 없다.

 

5의 제곱근보다 작은 정수만 나누면 된다. 5의 제곱근은 2.XX이다.  2.XX * 2.XX 가 5이다. 2의 배수는 5보다 작거나 같을 가능성이 있다. 그러나 3과 4의 배수는 5보다 무조건적으로 크므로 계산할 이유가 사라진다. 그러므로 5의 제곱근보다 작은 2만 나누기 연산을 하면된다.

 

4. 코드

 

첫 번째 방법 : 아리스토테네스의 체

 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		
		boolean[] primeNumber = new boolean[1001];
		
		primeNumber[0] = true;
		primeNumber[1] = true;
			// 아리스토 테네스의 체 
		for(int i=2;i<primeNumber.length;i++) {
			if(!primeNumber[i]) {
				int j = 2;
				while( primeNumber.length > j*i) { // 각 i의 배수들 true 저장
					primeNumber[j*i] = true;
					j++;
				}
			}
		}
		
		Scanner sc = new Scanner(System.in);
		int num = sc.nextInt();
		int count = 0;
		for(int i=0; i<num;i++)	{
			int value = sc.nextInt();
			if(!primeNumber[value]) count++;
		}
		
		System.out.println(count);
	}

}

 

 

두 번째 방법 : 제곱근

 

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

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer stz;
		
		int size = Integer.parseInt(br.readLine());
		stz = new StringTokenizer(br.readLine());
		int count = size;
		
		for(int i=0; i<size;i++) {
			int value = Integer.parseInt(stz.nextToken());
			
			if(value != 1) { 		
				for(int j=2; j*j <= value; j++) { // j의 제곱이 value를 넘어서면 계산할 이유가 없다.
					if(value % j == 0) { // 나머지가 0이면 소수가 아니다.
						count--;
						break;
					}
				}
			}else {
				count--; // 1은 소수가 아니다.
			}
			
			
		}
		
		bw.write(count+"\n");
		bw.flush();
		bw.close();
		br.close();
		
		
	}

}