백준 1929, 소수 구하기

문제

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

1929번: 소수 구하기

 

문제요약

1. M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

2. (1 ≤ M ≤ N ≤ 1,000,000)

 

문제풀이

소수판별 방법 중에서 간단한 방법으로는 어떤 수 N의 양의 제곱근 이하의 수들로 N을 나눠서 한번이라도 나누어 떨어지면 합성수(소수아님), 아니면 소수라고 판정하는 방법이 존재합니다. 즉, 어떤 수 N이 주어지면 2~N의 제곱근까지 나누어보았을때 N이 한번이라도 나누어 떨어지면 N은 합성수입니다.

 

소스코드

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


public class Main {
	public static boolean isPrime(int n)
	{	
		for(int i=2;i<=(int)Math.sqrt(n);i++)
		{
			if(n%i==0)
			{
				return false;
			}
		}
		return true;
	}

	public static void solution(int start, int end)
	{
		for(int i=start; i<=end; i++)
		{
			if(isPrime(i) && i>1)
			{
				System.out.println(i);
			}
		}
	}
	
	public static void main(String args[]) throws IOException
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String str[] = br.readLine().split(" ");
		int start = Integer.parseInt(str[0]);
		int end = Integer.parseInt(str[1]);
		
		solution(start, end);
		
	}
}

 

References

https://ko.wikipedia.org/wiki/%EC%86%8C%EC%88%98%ED%8C%90%EB%B3%84%EB%B2%95