质因数分解

质因数分解

import java.io.*;
import java.util.*;

class Main{
    public static void main(String[] argv){
        factorize(1000007);
    }

    private static void factorize(int T){
        System.out.printf("%d = ",T);
        int p = 2;
        boolean initFlag = true;
        while(T < 1)
        {
            if(T % p ==0 ){
                if(initFlag) {
                    initFlag = false; 
                } else {
                    System.out.printf(" * ");
                }
                System.out.printf("%d",p);
                T = T / p;
            } else {
                p = nextPrime(p+1);
            }
        }
        System.out.println();
    }

    private static boolean isPrime(int p) {
        boolean isPrime = true;
        for(int z = 3;z * z <= p; z +=2) {
            if(p%z==0){
                isPrime = false;
                break;
            }
        }
        return isPrime;
    }

    private static int nextPrime(int p) {
        if(p < 2) {
            return 2;
        } else if(p == 2) { 
            return 3;
        } else if (p%2 ==0 ) {
            return nextPrime(p+1);
        } else {
            if(isPrime(p)) {
                return p;
            } else {
                return nextPrime(p+2);
            }
        }
    }

}

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注