신규 블로그를 만들었습니다!

2020년 이후부터는 아래 블로그에서 활동합니다.

댓글로 질문 주셔도 확인하기 어려울 수 있습니다.

>> https://bluemiv.tistory.com/

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

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

 

문제

정수 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 :: 자바를 이용한 최댓값과 총 합 구하기, 간단하지만 알아야 하는 코딩

너무나 쉬운 프로그램이지만, 알고리즘 문제를 풀다보면 자주 쓰는 기능이므로 필수적으로 알아두는것이 좋다. 최댓값 구하기 // 최댓값 구하기 for(int i=0; i<n; i++)="" {="" if(max="" <="" data[i])="" max="data[i];" }="" }..<="" p=""> </n;>

hongku.tistory.com

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

 

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

너무나 쉬운 프로그램이지만, 알고리즘 문제를 풀다보면 자주 쓰는 기능이므로 필수적으로 알아두는것이 좋다. 문제 n개의 정수를 입력받아 배열에 저장한다. 배열을 오른쪽으로 1칸씩 Shift 한다. 전체 코드 1 2..

hongku.tistory.com

 

  • 네이버 블러그 공유하기
  • 네이버 밴드에 공유하기
  • 페이스북 공유하기
  • 카카오스토리 공유하기