JAVA 알고리즘 : 소수 판별하기

스터디사이트 : https://www.hackerrank.com

JAVA 알고리즘 : 소수 판별하기

입력된 수가 소수인지 판별하는 코딩을 완성하시오.

오랜만에 주어진 코딩이 없이 백지로 시작해야 한다. ㅋㅋ

※ 소수 :  1과 그 수 자신 이외의 자연수로는 나눌 수 없는 자연수

입력되는 숫자의 맨 첫번째는 입력될 숫자의 자릿수이다. → T

두번째부터 입력되는 숫자는 소수가 판별될 숫자이다. → n

소수가 맞다면 "Prime"을 출력

소수가 아니라면 "Not prime"을 출력시킨다.

입력

3

12

5

7

출력

Not prime

Prime

Prime

디버깅

소수판별 이라 하니..

정보처리기사의 소수판별 알고리즘이 빡 생각이 난다..

약수판별알고리즘

입력받는 숫자는 1부터 N까지 반복해가며 소수를 판별하기위해 입력받는 숫자 N이다.

변수 D는 변수 L이 소수인지 판별하기 위해 나누어 주어야 하는 수이다. 1은 모든 수의 약수이므로 D는 2 부터 L을 나눈다. L을 D로 나누어서 나머지 R이 0이 될때까지 반복한다. L을 D로 나누어 떨어졌을 때 (R=0), L과 D가 같다면 자신만 약수로 갖는 경우이므로 소수로 판별. 만약 L=20, D=2로 두었을 때, MOD(L, D) = MOD(20, 2) = 0 이라서 R=0이지만, L = D는아니다. → 20 != 2 20은 약수가 1과 20말고도 더 있지 않나. 그래서 약수가 아닌 것이다.

그러나 위 알고리즘은 1부터 입력된 수까지 1씩 증가시키면서 소수를 판별 시키는 것이고,

우리가 풀어야 할 문제는 입력된 숫자가 소수인지 아닌지 곧바로 판별을 해야 한다.

디버깅을 추가한 코딩을 실행 해 보면 이렇다.

2부터 1씩 증가시키는 int변수가 입력된 변수와 일치하지 않는데, 나머지가 0이라면 그 int변수로 나누어 떨어지게 된다는 의미 아닌가.

예를들어 12를입력했는데 int변수가 2일 경우 12가 2와 나누어 떨어지므로 이 수는 소수가 아니게 된다.

그러면 과감하게 while문을 빠져나가는 break문을 사용한다.

public static String discriminate(int num){ int i=2; String isPrime=null; while(i<=num){ System.out.println("i : " + i + ", num : " + num + ", i<=num - " + (i<=num) + ", i==num - " + (i==num) + ", i!=num - " + (i!=num) + ", num%i : " + (num%i)); if(num%i==0 && i==num) {System.out.println("Prime"); isPrime="Prime";} if(num%i==0 && i!=num) {System.out.println("Not prime"); isPrime="Not prime"; break;} i++; } return isPrime; } //end discriminate public static void main(String[] args) { Scanner scan = new Scanner(System.in); int T = scan.nextInt(); while(T-->0){ int num=scan.nextInt(); System.out.println("결과! : " + discriminate(num)); } //end while }

입력 :  3 12 5 7 결과 :  i : 2, num : 12, i<=num - true, i==num - false, i!=num - true, num%i : 0 Not prime 결과! : Not prime i : 2, num : 5, i<=num - true, i==num - false, i!=num - true, num%i : 1 i : 3, num : 5, i<=num - true, i==num - false, i!=num - true, num%i : 2 i : 4, num : 5, i<=num - true, i==num - false, i!=num - true, num%i : 1 i : 5, num : 5, i<=num - true, i==num - true, i!=num - false, num%i : 0 Prime 결과! : Prime i : 2, num : 7, i<=num - true, i==num - false, i!=num - true, num%i : 1 i : 3, num : 7, i<=num - true, i==num - false, i!=num - true, num%i : 1 i : 4, num : 7, i<=num - true, i==num - false, i!=num - true, num%i : 3 i : 5, num : 7, i<=num - true, i==num - false, i!=num - true, num%i : 2 i : 6, num : 7, i<=num - true, i==num - false, i!=num - true, num%i : 1 i : 7, num : 7, i<=num - true, i==num - true, i!=num - false, num%i : 0 Prime 결과! : Prime

그러나 완벽한 코딩 성공이 아니었다..

아래 두가지 케이스에서는 실패했다.

입력1 에서는

본인이 코딩을할때 시작값을 2부터 시작해서 입력된 1에 대한 해당조건이 아무것도 없어서 isPrime 문자의 첫 설정인 null이 그대로 출력이 된 것이고,

입력2 에서는

1씩 증가하면서 비교를하다보니 비교시간이 너무 오래걸렸다.

	입력 1	출력 1	입력 2	출력 2
모범결과	1 1	Not prime	10 1000000000 1000000001 1000000002 1000000003 1000000004 1000000005 1000000006 1000000007 1000000008 1000000009	Not prime Not prime Not prime Not prime Not prime Not prime Not prime Prime Not prime Prime
본인결과	null		시간초과

디버깅 2

입력값과 나누는 값 말고 count를 하는 int값을 하나 더 추가해서 반복을 시키니 null값이 나왔던 결과는 이제 정상으로 나온다.

문제는 이제 거대한 수를 입력했을때 빠르게 결과를 어떻게 나오게 할 것이냐다..

public static String discriminate(int num){ int i=2; int d=1; String isPrime=null; while(d<=num){ if(num%i==0 && i==num) {isPrime="Prime";} if(num==1 || num%i==0 && i!=num) {isPrime="Not prime"; break;} i++; d++; } return isPrime; } //end discriminate public static void main(String[] args) { Scanner scan = new Scanner(System.in); int T = scan.nextInt(); while(T-->0){ int num=scan.nextInt(); System.out.println(discriminate(num)); } //end while } //end main

입력 :  1 1 결과 :  Not prime

디버깅 3

큰 수를 빠른 계산을 시키기 위해서 제곱근을 사용하기로 했다.

Math.sqrt(Integer) 를 이용해서..

아래 코딩은 discriminiate() 메소드만 기재했다. main()메소드의 내용은 위와 같으니까..

그치만 안되는 케이스를 또 발견했다..

public static String discriminate(int num){ String isPrime=null; int sq = (int)Math.sqrt(num); System.out.println("sqrt("+num+") : " + sq); if(num%sq==0){isPrime="Not prime";}else{isPrime="Prime";} for(int i = 3; i <= sq; i+=2) { if(num%i == 0) { System.out.println("num : " + num + ", i : " + i + "--Not prime"); isPrime="Not prime"; break; }else{ System.out.println("num : " + num + ", i : " + i + "--Prime"); isPrime="Prime"; } } return isPrime; } //end discriminate

입력 :  2 79 10 결과 :  sqrt(79) : 8 num : 79, i : 3--Prime num : 79, i : 5--Prime num : 79, i : 7--Prime Prime sqrt(10) : 3 num : 10, i : 3--Prime Prime ( ← Not prime이여야 하는데!! )

디버깅 3

10의 제곱근은 3인데 ,

for문에서는 필터링을 다 한것으로 인식해서 더이상 짝수로 나머지를 구하지 않기때문에

10이 그냥 Prime으로 되는 것이다.

그래서 조건에다가 num % 2 를 추가해서 해결했다.

그리고 발견한 또다른 문제.. ㅋㅋㅋ ㅠㅠㅠㅠ

기본 소수중의 하나인 2가 Not Prime이라니...

public static String discriminate(int num){ String isPrime=null; int sq = (int)Math.sqrt(num); System.out.println("sqrt("+num+") : " + sq); if(num%sq==0){isPrime="Not prime";}else{isPrime="Prime";} for(int i = 3; i <= sq; i+=2) { if(num%i == 0 || num%2 ==0) { System.out.println("num : " + num + ", i : " + i + "--Not prime"); isPrime="Not prime"; break; }else{ System.out.println("num : " + num + ", i : " + i + "--Prime"); isPrime="Prime"; } } return isPrime; } //end discriminate

입력 :  1 2 결과 :  sqrt(2) : 1 Not prime ( ← Prime인데.... )

결과

public static String discriminate(int num){ String isPrime=null; int sq = (int)Math.sqrt(num); if(num==2 || num==3){ isPrime="Prime"; }else{ if(num%sq==0){isPrime="Not prime";}else{isPrime="Prime";} for(int i = 3; i <= sq; i+=2) { if(num%i == 0 || num%2==0) { isPrime="Not prime"; break; }else{ isPrime="Prime"; } //end if } //end for } //end if return isPrime; } //end method discriminate public static void main(String[] args) { Scanner scan = new Scanner(System.in); int T = scan.nextInt(); while(T-->0){ int num=scan.nextInt(); System.out.println(discriminate(num)); } //end while }

입력 :  3 12 5 7 1 2 1 1 10 1000000000 1000000001 1000000002 1000000003 1000000004 1000000005 1000000006 1000000007 1000000008 1000000009 2 79 10 2 29 22 결과 :  Not prime Prime Prime  Prime Not prime Not prime Not prime Not prime Not prime Not prime Not prime Not prime Prime Not prime Prime Prime Not prime Prime Not prime