1~100범위 안에 가장 큰 소수 구하기

소수는 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다. 예를 들어, 5는 1×5 또는 5×1로 수를 곱한 결과를 적는 유일한 방법이 그 수 자신을 포함하기 때문에 5는 소수이다. 그러나 6은 자신보다 작은 두 숫자(2×3)의 곱이므로 소수가 아닌데, 이렇듯 1보다 큰 자연수 중 소수가 아닌 것은 합성수라고 한다. 1과 그 수 자신 이외의 자연수로는 나눌 수 없는 자연수로 정의하기도 한다.

 

문제의 코드는 소수인지 판별하기 위해 제곱근까지의 숫자로 나누어 떨어지는 지 검사한다.

제곱근까지의 수 중 한 개의 수에 대해서라도 나누어 떨어지면 소수가 아니다.

예를 들어 25는 2,3,4,5로 나누었을 때 5로 나누어 떨어지므로 소수가 아니고, 41은 2,3,4,5,6으로 나누어도 한 번에 나누어 떨어지지 않으므로 소수이다.

---

코드

1  import java.lang.Math;

2  public class Test{
3      public static void main(String[] args){
4          int p = 2;
        
5          int n = 3;
6          while(true){
7              double t = Math.sqrt(n);
            
8              int m = (int)t;
9              for(int i=2; i<m; i++){
10                  int r = n % i;
11                  if(r==0)
12                      break;
13                  if(i==m)
14                      p=n;
15              }
16              n++;
17              if(n>100)
18                  break;
19          }
20          System.out.printf("%d\n", p);
21      }
22  }

---

결과

97

---

설명

1열 : sqrt()메소드가 정의되어 있는 헤더파일이다.

4열 : 소수를 저장할 변수 p를 선언하고 숫자 1과 2는 이미 소수라고 판단되었음을 가정한다.

5열 : 3부터 100까지의 수를 저장할 정수형 변수 n을 선언하고 3으로 초기화한다.

6열 : 조건을 만족하는 동안 반복, 조건이 true이므로 무한 반복한다. break를 만나기 전까지 반복

7열 : 배정도 실수형 변수 t를 선언하고, Math클래스의 sqrt() 메소드를 사용하여 n의 제곱근을 1에 저장

※ Math.sqrt(n) : n의 제곱근 값을 반환

8열 : 정수형 변수 m을 선언하고 1의 값을 정수로 변환하여 저장

9열 : 소수 판별을 위한 for 반복문의 시작이다. 반복 변수 i가 2에서 시작하여 1씩 증가하면서 m보다 작거나 같은 동안         아래를 반복

10열 : 정수형 변수 r을 선언하고 n을 i로 나눈 나머지를 저장

11열 : r의 값이 0과 같으면 소수가 아니므로 for문을 빠져나간다.

12열 : for문을 벗어나 16열로 이동한다.

13열 : i와m의 값이 같으면 n은 소수이므로 p에 n을 저장한다.

17열 : n의 값이 100보다 크면 15열을 수행한다.

18열 : while문을 벗어나 20열로 이동한다.