소수를 구하는 법

저번에는 Java로 최대공약수와 최소공배수를 구하는 방법에 대해 썼습니다.

이번에는 소수를 구하는 방법에 대해서 글을 써보겠습니다.

소수를 구하는 방법은 많습니다. 저는 그 중에서 많이 알려진 에라토스테네스의 체를 이용하여 구현해보겠습니다.

import java.io.*;
import java.util.*;
public class Main {
    public static boolean[] prime;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int A = Integer.parseInt(br.readLine());

        setPrime(A);

        if(!prime[A]) {
            System.out.println("소수입니다");
        } else {
            System.out.println("소수가 아닙니다");
        }
    }
    public static void setPrime(int A) {

        prime = new boolean[A+1];

        for (int i = 2; i <= Math.sqrt(A); i++) {

            if(prime[i]) {
                continue;
            }

            for (int j = i*i; j < prime.length; j+=i) {
                prime[j] = true;
            }
        }
    }
}

수를 하나 입력 받은 후에 그 수가 소수인지 아닌지를 판별하는 코드입니다. 에라토스테네스 체에 관련한 자세한 풀이가 궁금하시다면 다른 분들의 포스팅을 봐주시길 바랍니다 저도 엄청 자세히는 모르는 내용이라서 ㅎㅎ

 

A 이상 B이하의 소수들을 구하는 구하는 알고리즘이고 이와 관련된 백준 문제도 있어서 그 문제의 풀이 방법을 참고했습니다. 

1929번: 소수 구하기 (acmicpc.net)

1929번: 소수 구하기

import java.io.*;
import java.util.*;
public class Main {
    public static boolean[] prime;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int A = Integer.parseInt(br.readLine());
        int B = Integer.parseInt(br.readLine());

        prime = new boolean[B + 1];
        setPrime();
        for (int i = A; i <= B; i++) {

            if(!prime[i]) {
                System.out.println(i);
            }
        }

    }
    public static void setPrime() {


        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;
            }
        }
    }
}