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

소수를 구하는 문제는 굉장히 중요한 문제이다.

문제해결에 도움이 많이 되는 코딩이므로 알아두자!

 

문제

정수 n을 입력받아

n까지 모든 소수 구하기

 

 

힌트

k의 소수를 구하기 위해,

 

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

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

 

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

2부터

까지 살펴보면 된다.

 

전체 코드

package exam03;

import java.util.Scanner;

/**
 * [뮨제]
 * n을 입력받아 n전까지의 소수 모두 구하기
 * @author hongku
 *
 */
public class Ex03 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        
        for(int i=2; i<=n; i++) {
            boolean isPrime = true; // 초기 값
//            for(int j=2; j<=i/2; j++) {
            for(int j=2; j*j<=i; j++) {
                if(i % j == 0) {
                    // 소수가 아니다.
                    isPrime = false;
                    break;
                }
            }
            
            if(isPrime) {
                // 소수 일때만 값을 출력
                System.out.print(i + " ");
            }
        }
        
        sc.close();
    }
}​

 

isPrime boolean 변수를 통해,

소수인지 아닌지 판단한다.

 

21번째 줄 for문을 살펴보면,

루트를 표현하기위한 방법으로

j * j <= i 와 같이 표현했다.

 

사실 java의 Math 라이브러리에 Math.sqrt() 메소드를 이용하면 루트(root)를 구할 수 있지만,

위에서는 굳이 라이브러리를 사용안해도 표현이 가능하다.

 

 

 

관련 글

2018/05/09 - [Language/JAVA] - JAVA :: 자바를 이용한 최댓값과 총 합 구하기, 간단하지만 알아야 하는 코딩

JAVA :: 자바를 이용한 최댓값과 총 합 구하기, 간단하지만 알아야 하는 코딩

2018/05/09 - [Language/JAVA] - JAVA :: 자바를 이용한 배열 Shift하기, 간단하지만 알아야 하는 코딩

JAVA :: 자바를 이용한 배열 Shift하기, 간단하지만 알아야 하는 코딩