Baekjoon1978: 소수 찾기

Baekjoon1978: 소수 찾기

문제

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

입력

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

출력

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

추상화

역시 제한조건이 중요하다. 수의 크기는 1,000이하의 자연수이다

미리 배열을 통해 소수를 가려낼 수 있다

1) 논리배열을 만든다. 처음 값은 모두 false이다

2) 소수가 아닌 숫자를 true로 만들어준다

3) 어떤 숫자에 2, 3 등을 곱한 결과값은 소수가 아니다

4) 반복문 안에서 모든 숫자에 대해 값을 곱하고 해당값을 논리배열에 표시해준다

5) 소수인지 묻는 입력값에 대해 해당하는 값을 논리배열 index와 대조하여 답을 구한다

import java.io.*; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); boolean[] prime = new boolean[1001]; int devide =0; int num = 0; int sum=0; //소수 배열 만들기, 반복문에서 사용되는 변수 미리 만들기 for(int i=2; i<1001; i++) { devide = 1000/i; for(int j=2; j<=devide; j++) { prime[i*j] = true; //false로 남은 애들만 소수다. 2부터 곱해주는 것을 잊지말자 } } prime[0] = true; prime[1] = true; //0과 1은 특별히 구분해서 소수가 아님을 표시한다 int N = Integer.parseInt(br.readLine()); StringTokenizer st = new StringTokenizer(br.readLine()," "); for(int i=0; i

from http://devyoseph.tistory.com/59 by ccl(A) rewrite - 2021-10-13 09:27:58