[백준/JAVA] 1978번: 소수 찾기
🔺 문제
1978번: 소수 찾기
첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.
www.acmicpc.net
🔺 코드
- 방법1)
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int n = Integer.parseInt(br.readLine());
int[] arr = new int[n];
int cnt = 0;
st = new StringTokenizer(br.readLine(), " ");
for(int i=0 ; i < n ; i++) {
arr[i] = Integer.parseInt(st.nextToken());
boolean flag = true;
if(arr[i] == 1) flag = false;
for(int j = 2 ; j <= Math.sqrt(arr[i]) ; j++) {
if(arr[i] % j == 0) {
flag = false;
break;
}
}
if(flag) cnt++;
}
System.out.println(cnt);
}
}✅ 해결 아이디어
- 소수 여부를 boolean으로 표시 → 소수이면 true / 소수가 아니면 false로
- 입력받은 값이 1이라면, 소수가 아니게 처리 (20번째 줄)
- 방법2) 에라토스테네스의 체 이용
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
import java.util.*;
import java.io.*;
public class Main {
public static final int MAX = 1001;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 에라토스테네스의 체
boolean[] isPrime = new boolean[MAX];
for(int i = 2 ; i < MAX ; i++) {
isPrime[i] = true;
}
for(int i = 2 ; i <= Math.sqrt(MAX) ; i++) {
for(int j = i * i ; j < MAX ; j += i) {
if(!isPrime[j]) continue;
isPrime[j] = false;
}
}
int n = Integer.parseInt(br.readLine());
int cnt = 0;
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
for(int i = 0 ; i < n ; i++) {
int x = Integer.parseInt(st.nextToken());
if(isPrime[x]) cnt++;
}
System.out.println(cnt);
}
}
|
cs |
🔺 다른 풀이들
[백준] 1978번 : 소수 찾기 - JAVA [자바]
https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 문제 드디어 새로운 카
st-lab.tistory.com
여러가지 풀이 방법... 그 중에서도 에라토스테네스의 체를 사용한 코드가 있음!
(참고)
✔ 프로그래머스 - 소수 찾기
[프로그래머스/Lv. 1] 소수 찾기
🔺 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr
bono039.tistory.com
✔ 에라토스테네스의 체
[알고리즘] 소수(Prime Number) 구하기 - 에라토스테네스의 체 (Java)
소수 소수(prime number)는 정수론의 가장 중요한 연구 대상 중 하나로, 양의 약수가(1보다 큰 자연수) 1과 자기 자신만을 약수로 가지는 수를 의미한다. 소수의 반대말로, 세 개 이상의 양의 약수를
loosie.tistory.com
[백준 1978] 소수 찾기
글에 개요 백준 알고리즘 1978번 "소수 찾기" 문제입니다. 에라토스테네스의 체 개념을 알면 쉽게 해결할 수 있습니다.앞서 다루었던, 아래 참고할 글 1번에 정리한 내용을 보시면 쉽게 푸실 수 있
brenden.tistory.com
(+ 6/12 2회독)
계속 풀고 계속 틀리는 에라토스테네스의 체ㅎ
본체만체 하고 싶다
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
import java.util.*;
import java.io.*;
public class Main {
static final int MAX = 1001;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
boolean[] isPrime = new boolean[MAX];
Arrays.fill(isPrime, true);
isPrime[0] = isPrime[1] = false;
for(int i = 2 ; i <= Math.sqrt(MAX) ; i++) {
if(!isPrime[i]) continue; // 이미 체크된 배열이면 skip
for(int j = i * i ; j < MAX ; j += i) {
isPrime[j] = false;
}
}
int n = Integer.parseInt(br.readLine());
int cnt = 0;
StringTokenizer st = new StringTokenizer(br.readLine()," ");
while(n --> 0) {
int x = Integer.parseInt(st.nextToken());
if(isPrime[x]) cnt++;
}
System.out.println(cnt);
}
}
|
cs |
