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

소수 찾기 

 

문제

주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.

 

입력

첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.

 

출력

주어진 수들 중 소수의 개수를 출력한다.

 

예제 입력 1 

4
1 3 5 7

예제 출력 1 

3

 

---

우선 내가 푼 방식. 

입력받는 수는 1000이하의 값 이므로 1001의 크기를 가진 정수 배열을 생성했다. (인덱스를 받아온 숫자 그대로 이용하기 위해 1001로 설정) 여기에 소수인 값이면 해당 인덱스에 1을 저장할 것이다.

 

받아온 수에서 짝수(2 제외)이면 소수가 아니므로 while문에서 2+홀수 인 경우 해당 인덱스에 1을 넣어줬다.

그리고 홀수들의 배수이면 소수가 아니므로,  for문을 이용해 3부터 시작해서  0 값을 넣어주도록 했다.

즉 i=3인 경우 안에 while문을 통해 6, 9, 12 , ,,, 인덱스의 값을 0으로 바꿔주고, 증감식을 통해 i=5로 바뀌고 10, 15, 20,,, 인덱스의 값을 0으로 바꿔주는 방식으로 했다.

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());

		int limit = 1000; // 입력하는 수는 1000 이하임
		int[] numArr = new int[limit + 1]; // 입력하는 수 담을 수 있는 배열 생성.

		while (st.hasMoreTokens()) {
			int num = Integer.parseInt(st.nextToken());
			if (num % 2 != 0 || num == 2) { // 짝수(2 제외)면 소수 아니므로 제외함
				numArr[num] = 1;
			}
		}

		numArr[1] = 0;
		for (int i = 3, j = 1; i * ++j <= limit; i += 2) {
			while (i * ++j <= limit) {
				numArr[i * j] = 0;
			}
			j = 1;
		}

		int cnt = (int) Arrays.stream(numArr).filter(num -> num == 1).count();

		bw.write(cnt + "");
		bw.flush();
		bw.close();
		br.close();
	}
}

 

---

다음은 다른분들 코드를 참조해 수정한 코드이다.

 

소수인지 여부를 확인하는 변수 primeNum을 두고, for문에서 2부터 시작해 해당 num의 제곱근까지의 수로 나눴을 때 나머지가 없는 경우 소수가 아니라고 보고 계산하도록 했다.

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());

		int cnt = 0;
		while (st.hasMoreTokens()) {
			int num = Integer.parseInt(st.nextToken());
			boolean primeNum = true;

			if (num == 1) {
				continue;
			}

			for (int i = 2; i <= Math.sqrt(num); i++) {
				if (num % i == 0) {
					primeNum = false;
					break;
				}
			}
			if (primeNum == true) {
				cnt++;
			}
		}

		bw.write(cnt + "");
		bw.flush();
		bw.close();
		br.close();
	}
}

---