[알고리즘] 백준 1978
[문제] : 100 이하의 숫자들 소수 판별하기
[풀이1] : 숫자 N 에 대하여 N-1 까지 일일히 나누기
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
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());
st = new StringTokenizer(br.readLine());
int count = 0;
for (int i = 0; i < N; i++) {
int n = Integer.parseInt(st.nextToken());
if(isPrime(n)) count++;
}
System.out.println(count);
}
static boolean isPrime(int number){
if(number==1){
return false;
}
for (int i = 2; i < number; i++) {
if(number%i ==0) return false;
}
return true;
}
}
[풀이2] : 만약 숫자 N 이 공약수를 가지고 있으면 A * B 의 형태일 것이고, 그러면 A, B 중 하나는 Math.sqrt(N) 보다 작을 것이다 라는 것으로 풀기
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
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());
st = new StringTokenizer(br.readLine());
int count = 0;
for (int i = 0; i < N; i++) {
int n = Integer.parseInt(st.nextToken());
if(isPrime(n)) count++;
}
System.out.println(count);
}
static boolean isPrime(int number){
if(number==1){
return false;
}
for (int i = 2; i <= Math.sqrt(number); i++) {
if(number % i == 0) return false;
}
return true;
}
}
[풀이3] : 에레토스테네스의 체 ( 가장 일반적인 방법이다 )
public class Eratosthenes {
static boolean[] arr;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
checkPrime(N);
}
static void checkPrime(int N){
arr = new boolean[N];
if(N < 2) return;
// true 면 소수 x, false 면 소수
arr[0] = arr[1] = true;
for (int i = 2; i <= Math.sqrt(arr.length); i++) {
if(arr[i]) continue;
for (int j = i * i; j < arr.length; j += i) {
arr[i] = true;
}
}
}
}
참고 : https://st-lab.tistory.com/80
Author And Source
이 문제에 관하여([알고리즘] 백준 1978), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@xpmxf4/알고리즘-백준-1978저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)