728x90
반응형
▷ 문제
자연수 N이 입력되면 1부터 N까지의 소수의 개수를 출력하는 프로그램을 작성하세요.
만약 20이 입력되면 1부터 20까지의 소수는 2, 3, 5, 7, 11, 13, 17, 19로 총 8개입니다.
* 입력
첫 줄에 자연수의 개수 N(2<=N<=200,000)이 주어집니다.
* 출력
첫 줄에 소수의 개수를 출력합니다.
▷ 입력 예시
20
▷ 출력 예시
8
▷ 풀이
1. 자기 자신보다 작은 모든 수로(>=2) 나누어 소수인지 판별
import java.util.Scanner;
public class Main {
public int solution(int[] arr){
int answer = 0;
for (int i = 0; i < arr.length; i++) {
if(isPrime(arr[i])){
answer++;
};
}
return answer;
}
public static boolean isPrime(int n){
if(n == 1){
return false;
}
for(int i=2; i<n; i++){
if(n%i == 0){
return false;
}
}
return true;
}
public static void main(String[] args) {
Main main = new Main();
Scanner kb = new Scanner(System.in);
int n = kb.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = i+1;
} // 1~n
kb.close();
System.out.println(main.solution(arr));
}
}
2. 에라토스테네스 체를 통한 소수 판별
* 에라토스테네스 체 : https://firework-ham.tistory.com/8
import java.util.Scanner;
public class Main {
public int solution(int n){
int answer = 0;
int[] arr = new int[n+1];
for (int i=2; i<=n; i++) {
if(arr[i]==0){
answer++;
for(int j=i ; j<=n ; j=j+i){
arr[j] = 1;
}
}
}
return answer;
}
public static void main(String[] args) {
Main main = new Main();
Scanner kb = new Scanner(System.in);
int n = kb.nextInt();
kb.close();
System.out.println(main.solution(n));
}
}
▷ 핵심 포인트
1. 소수 판별은 에라토스테네스 체가 성능면에서 가장 우수하므로 가능하면 이 방법을 사용하며 풀어줍니다.
반응형
'Algorithm > Array' 카테고리의 다른 글
[알고리즘]점수계산 - 연속적으로 답을 맞힌 경우 가산점 주기 (0) | 2021.10.15 |
---|---|
[알고리즘]숫자 거꾸로 뒤집기, 소수 판별 (0) | 2021.10.14 |
[알고리즘]피보나치 수열 (0) | 2021.10.13 |
[알고리즘]가위바위보 (0) | 2021.10.13 |
[알고리즘]큰 수 출력하기 - 배열에서 자신의 앞에 있는 수들 보다 클 경우에만 카운트하기 (0) | 2021.10.12 |