[백준 1929 JAVA 자바] 소수 구하기

m 이상 n 이하의 소수를 모두 출력하는 프로그램

 

소수를 판정하는 방법에는 여러가지가 있지만

가장 간단한건

대상 숫자인 A를

2부터 A-1까지 나눠보는겁니다

% 로 나눳을 때 나머지가 없으면

나누어 떨어진다는 뜻이고

소수가 아니다! 라고 할 수 있거든요

 

코드입니다

 

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int a = Integer.parseInt(st.nextToken());
		int b = Integer.parseInt(st.nextToken());
		
		for(int i=a;i<=b;i++) {
			if(isprime(i)==1) {
				System.out.println(i);
			}
		}
	}  

	static int isprime(int m) {
		if (m==0 || m==1) 
		{
			return 0;
		}
		for (int i=2;i<=(int)(Math.sqrt(m));i++) {
			if (m%i==0) {
				return 0;
			}
		}
		return 1;
	}
}

저는 m-1 까지 나눈게 아니고

Math.sqrt(m)까지 나눴습니다

(Math.sqrt(m)은 루트m입니다)

 

그 이유는 1~루트m에 약수가 있다면

루트m~m-1에도 약수가 있고

1~루트m에 약수가 없다면

루트m~m-1에도 약수가 없기 때문입니다