2024.06.11 ( Java )

1. 에라토스테네스의 체 ( BaekJoon )

Math ( https://www.acmicpc.net/problem/2960 )

풀이 ->

• 에라토스테네스의 체 -> 지울 수 있는 가장 작은 수 부터 지워가는 알고리즘 ( 이때 사이클 돌고 가장 작은 수가 소수다 wow )

package problem_solving.math;

import java.util.Arrays;
import java.util.Scanner;

public class BaekJoon_2960 {

	static int [] arr ;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = Integer.parseInt(sc.next());
		int k =Integer.parseInt(sc.next());
		arr = new int[n+1];
		for(int i= 2 ; i < arr.length;i++) {
			arr[i] = i;
		}
		int cnt = 0 ; 
		
		
		int i = 1 ; 
		
		
		int num = 2;  
		
		int index = num ;
		
		while(true) {
		
			
			

			if( (num * i) <= n ) {
				int answer  = 0 ;
				if( arr[index] !=0) {										
					cnt++;
					answer = arr[index];
					arr[index] = 0 ;
				}
				if( cnt == k ) {
					System.out.println(answer);
					break;
				}
				
				i++;
				index = num *i ; 
			}else {				
				int min = checkMin();
				num = min ; 
				i = 1; 
				index = num ; 
			}
			
		}
		
		
	}
	
	public static int checkMin() {
		for(int i = 2;  i < arr.length;i++) {
			if( arr[i] != 0) {
				return arr[i];
			}
		}
		return 1;
	}
	
	

}

2. 소수구하기 ( BaekJoon )

Math ( https://www.acmicpc.net/problem/1929 )

풀이 ->

• 주어진 수가 소수가 아니라면 그 수의 제곱근 또한 약수를 갖기 때문에 시간을 줄이기위해 i*i 조건 설정

package problem_solving.math;

import java.util.Scanner;

public class BaekJoon_1929 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int m = Integer.parseInt(sc.next());
		int n = Integer.parseInt(sc.next());
		while(m<=n) {
			int cnt = 0 ;
			if( m == 1) {
				m++;
				continue;
			}
			for(int i= 1; i*i<=m ;i++) {
				if( cnt >= 2 ) {
					break;
				}
				if( m % i == 0 ) {
					cnt++;
				}
			}
			if( cnt == 1) {
				System.out.println(m);
			}
			m++;
			
		}
	}
	
	

}

백준 레벨 변동

• Gold 5 37% -> Gold 5 39%

풀이 유형

Math - 2문제