본문 바로가기
카테고리 없음

소인수분해

by DogBull 2007. 9. 27.
//매개변수 argLong의 소인수분해 결과를 출력한다.
    public void factorization(long argLong){
        long max=    (long)Math.sqrt(argLong)+1;

        long c=    argLong;

        while((c%2)==0){
            System.out.println(2);
            c=c/2;
        }

        long i=3;
        while(i<=max){
            if((c%i)==0){
                System.out.println(i);
                max=(long)Math.sqrt(c)+1;
                c=c/i;
            }else{
                i=i+2;
            }
        }

        if(c>i) System.out.println(c);
    }

아주 큰 정수에 대해 그 정수가 소수인지 판단하는데 매유 효율적인 확률화 알고리즘도 있다.
ex) public boolean BigInteger.isProbablePrime(int certainty)
이 BigInteger객체가 소수일 확률은 1-1/2^certainty 이다.