[Java] 백준 - 1929번: 소수 구하기

4월 18일(화)-약수, 소수와배수2(1929번)

1929번: 소수 구하기

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

8월 9일(화) - 8단계(1929번)

1. 작년에 C로 에라토스테네스의 체를 공부했던 내용이 거의 기억이 나지 않는걸로 보아서 제대로 이해를 못했었나보다

 

JAVA [자바] - 소수 구하는 알고리즘 및 구현

2. 따라서 관련 내용들을 다시 공부한 뒤에 풀이를 해보려했다

-> 풀이 - 1 그리고 풀이 - 2 모두 추후에 복습해볼 것

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이 - 1

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

import java.util.StringTokenizer;

public class Main{
    public static boolean[] prime;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

        prime = new boolean[N+1];
        get_prime();

        StringBuilder sb = new StringBuilder();
        for(int i=M; i<=N; i++)
        {
            if(!prime[i])
            {
                sb.append(i).append('\n');
            }
        }
        System.out.println(sb);
    }

    public static void get_prime(){
        prime[0] = prime[1] = true;

        for(int i=2; i<= Math.sqrt(prime.length); i++)
        {
            if(prime[i])
            {
                continue;
            }
            for(int j=i*i; j< prime.length; j+=i)
            {
                prime[j] = true;
            }
        }
    }
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이 - 2

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

import java.util.StringTokenizer;

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine()," ");

        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

        boolean[] prime = new boolean[N+1];

        for(int i=2; i<=N; i++)
        {
            if(prime[i])
            {
                continue;
            }
            if(i >= M)
            {
                sb.append(i).append('\n');
            }
            for(int j=i+i; j<=N; j+=i)
            {
                prime[j] = true;
            }
        }
        System.out.println(sb);
    }
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

풀이출처 -> https://st-lab.tistory.com/84