[050] 1929. 소수 구하기

✨ 알고리즘 분류 : 수학 / 정수론 / 소수 판정 / 에라토스네스의 

 

https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

---

 

 

🪡 문제에서 요구하는 조건 정리

 

- n 이상이고 m 이하인 소수를 모두 구한다

 

 

 

🧶 풀이과정 

 

우선, 소수를 구하는 방법은 저번 글에서 말했듯, 6이라고 한다면 제곱근이 6보다 큰 3*3 이전의 수, 2를 곱하는 식으로 진행한다.

계속해서 반복하는 것이므로 static을 만들어서 호출하는 방식을 사용했고, 판별하여 맞으면 수를 출력, 아니면 다음 수로 가는 형식으로 코드를 구현했다.

 

처음에는 리스트를 만들어서 그 리스트를 순회하는 방법을 생각했는데, 시간 초과가 계속 나오는 바람에 포기했다. 이와 같은 방법은 리스트를 우선 전체 다 순회하기 때문에 그렇다고 한다.

 

import java.io.*;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.StringTokenizer;

public class Main{

    static List<Integer> list = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());

        int fst = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());
        
        for(int i = 2; i <= end; i++){
            
            if(prime(i)){
                list.add(i);
                
                if(i >= fst) bw.write(i + "\n");
            }
        }



        bw.flush();
        bw.close();
        br.close();

    }

    public static boolean prime(int num){

        if(num <= 1) return false;

        for (int i : list) {
            if (i * i <= num) {
                if (num % i == 0) {
                    return false;
                }
            }
        }

//        for(int i = 2 ; i * i <= num; i++){
//            if(num % i == 0){
//                return false;
//            }
//        }

        return true;
    }
}

 

 

그래서 그냥 단순하게, for문을 num까지 돌리는 단순한 방법으로 가자고 하니 바로 성공

 

import java.io.*;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.StringTokenizer;

public class Main{

    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());

        int fst = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());
        
        for(int i = 2; i <= end; i++){
            
            if(prime(i)){

                
                if(i >= fst) bw.write(i + "\n");
            }
        }



        bw.flush();
        bw.close();
        br.close();

    }

    public static boolean prime(int num){

        if(num <= 1) return false;


        for(int i = 2 ; i * i <= num; i++){
            if(num % i == 0){
                return false;
            }
        }

        return true;
    }
}

 

 

근데 여기서 아주 작은 고민이 생겼다.

for문을 보면, 2부터 2 3 4 5 6 7 8 이렇게 전부 순회하니까 소수가 아닌 애들도 전부 곱하게 된다. 그러니까, 나는 이미 리스트로 하는 방법을 알고 있고, 소수를 판별하는 방법도 알고 있다.

 

그럼 시간은 당연히 줄일 수 있지 않을까? 하고 다시 코드를 생각해봤다.

아주 간단단하게, for문으로 도는 부분을 list화 시키면 되는 일이다!

 

 

🏹 제출코드

 

package data_structure_part_01;

import java.io.*;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.StringTokenizer;

public class Q1929 {

    static List<Integer> list = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());

        int fst = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());

        list.add(2);
        list.add(3);

        for(int i = 2; i <= end; i++){

            if(prime(i)){
                list.add(i);

                if(i >= fst) bw.write(i + "\n");
            }
        }



        bw.flush();
        bw.close();
        br.close();

    }

    public static boolean prime(int num){

        if(num <= 1) return false;

//        for (int i : list) {
//
//            if (i * i <= num) {
//                if (num % i == 0) {
//                    return false;
//                }
//            }
//        }

        for(int i = 0; list.get(i)* list.get(i) <= num; i++){


                if(num % list.get(i) == 0){
                    return false;
                }

        }

        return true;
    }
}

 

 

아주 성공적!

120ms 면 굉장히 큰 차이라고 볼 수 있다. 효율적 방법을 찾은 거 같아서 뿌듯 🍀