ING

안녕하세요 Jin's 입니다.

백준 알고리즘의 수학2 중 소수 구하기 ( 문제 번호 : 1929 )의 소스입니다.

Java와 Python 두가지 버전 소스입니다.

예시 ) 4  : 1 2 4

        12 : 1 2 3 4 6 12

* 제곱근의 루트보다 작은 수일때 약수가 존재하지 않는다면 소수이므로 찾는 범위를 반으로 줄여 시간을 줄일 수 있다. 

1) JAVA

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int m = scan.nextInt();
		int n = scan.nextInt();
		scan.close();
		
		for(int i=m; i<=n; i++){
			int result = 0;
			int x = (int)Math.sqrt(i);
			if(i==1) result++;

			for(int j=2; j<=x; j++){
				if(i%j==0){
					result++;
					break;
				}
			}
			
			if(result==0){
				System.out.println(i);
			}
		}
	}

}

2) PYTHON

import math
m, n = map(int, input().split())
for i in range(m, n+1):
    result = 0
    if i == 1:
        result += 1
        continue
    x = int(math.sqrt(i))
    for k in range(2, x+1):
        if i % k == 0:
            result += 1
            break

    if result == 0:
        print(i)

여러분도 한번 풀어보세요!