백준 1929번 소수구하기(Python, Java)

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

1929번: 소수 구하기

 

문제를 보자마자 바로 풀이가 떠올라고 구현을 시작하였다. 그런데? 소수를 구하는 방법에서 내가 효율적인 풀이방법이 떠오른 것은 아니고 그냥 일반적인 풀이를 떠올렸다. 그런데 시간초과가 뜬다. 뭐 고민을 해보다 구글링을 하였다.

구글링을 해보다 알게 된 사실은 소수판별은 해당 수의 제곱근까지만 나눠보면 된다는 것이다. 

 

 

 

n, m 사이의 소수구하는 팁 

 

k의 소수를 구하기 위해,

 

2부터 k/2까지 나눴을때 나누어지는 숫자가 존재하지 않으면 소수이다.

k의 약수는 k/2보다 클수가 없으므로!

 

수학적으로 좀 더 깊게 생각해보면(글쓴이는 수학적으로 깊게 생각하지 못해서 외우고 있다...)

2부터

까지 살펴보면 된다.

출처: https://hongku.tistory.com/176

JAVA :: n까지 모든 소수 구하기, 간단하지만 알아야 하는 코딩

 

위의 블로그에서 좋은 내용이 있어서 가져왔다. 그런데 나도 솔직히 수학을 잘하지 못해서 왜 인지는 잘 모르겠다. 

그냥 받아들이려고 한다...  이 내용을 알면 시간초과가 발생하지 않을 것이고 나중에 소수구하는 문제에서도 꿀팁으로 풀 수 있을 것 같다.

 

 

 

1. 소수 구하기(1929번) with Python  

 

import math
 
def isPrime(num):
    if num == 1:
        return False
 
    n = int(math.sqrt(num))
 
    for k in range(2, n+1):
        if num % k == 0:
            return False
    return True
 
# main
m, n = map(int, input().split())
for k in range(m, n+1):
    if isPrime(k):
        print(k)
 

 

2. 소수 구하기(1929번) with Java

 

import java.util.Scanner;
 
public class Prime {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
 
        int a = input.nextInt();
        int b = input.nextInt();
 
        for (int i = a; i <=b; ++i) {
            if (isprime(i)) {
                System.out.println(i);
            }
        }
 
    }
    static boolean isprime(int num) {
        if (num == 1) {
            return false;
        }
 
        int n = (int)Math.floor(Math.sqrt(num));
 
        for (int k = 2; k < n + 1; ++k) {
            if (num % k == 0) {
                return false;
            }
        }
        return true;
 
    }
}