題目內容: 每個非素數(合數)都可以寫成幾個素數(也可稱為質數)相乘的形式,這幾個素數就都叫做這個合數的質因數。比如,6可以被分解為2x3,而24可以被分解為2x2x2x3。 現在,你的程式要讀入一個[2,100000]範圍內的整數,然後輸出它的質因數分解式;當讀到的就是素數時,輸出它本身。 輸入格 ...
題目內容:
每個非素數(合數)都可以寫成幾個素數(也可稱為質數)相乘的形式,這幾個素數就都叫做這個合數的質因數。比如,6可以被分解為2x3,而24可以被分解為2x2x2x3。
現在,你的程式要讀入一個[2,100000]範圍內的整數,然後輸出它的質因數分解式;當讀到的就是素數時,輸出它本身。
輸入格式:
一個整數,範圍在[2,100000]內。
輸出格式:
形如:
n=axbxcxd
或
n=n
所有的符號之間都沒有空格,x是小寫字母x。
輸入樣例:
18
輸出樣例:
18=2x3x3
時間限制:500ms記憶體限制:32000kb
1 import java.util.Scanner; 2 3 public class Main { 4 5 public static void main(String[] args) { 6 // TODO Auto-generated method stub 7 Scanner in = new Scanner(System.in); 8 9 int n;//輸入整數 10 int nCopy;//複製n的值 11 int prime=2;//素數,第一個是2 12 int count=0;//輸出質因數個數 13 14 n=in.nextInt(); 15 16 if(prime(n)) 17 { 18 System.out.printf("%d=%d\n",n,n);//n=n 19 } 20 else 21 { 22 System.out.printf("%d=",n);//n=? 23 24 nCopy=n; 25 26 while(nCopy>1) 27 { 28 if(nCopy%prime==0) 29 { 30 if(count>0) 31 { 32 System.out.print("x"); 33 } 34 nCopy=nCopy/prime; 35 System.out.print(prime); 36 count++; 37 } 38 else 39 { 40 prime++;//跳過當前素數 41 prime=nextPrime(prime);//下一個素數 42 } 43 } 44 45 System.out.printf("\n");//換行 46 47 } 48 } 49 50 public static boolean prime(int n)//判斷是否素數 51 { 52 boolean isPrime=true;//假設n是素數 53 if(n==1||(n%2==0&&n!=2))//判斷1和非2偶數 54 { 55 isPrime=false; 56 } 57 else if(n==2)//判斷2 58 { 59 isPrime=true; 60 } 61 else//判斷其他 62 { 63 for(int i=3;i<Math.sqrt(n);i=i+2) 64 { 65 if(n%i==0) 66 { 67 isPrime=false; 68 break; 69 } 70 } 71 } 72 73 return isPrime; 74 } 75 76 public static int nextPrime(int n)//找下一個素數 77 { 78 while(true) 79 { 80 if(prime(n))//如果n是素數,返回n 81 { 82 return n; 83 } 84 else//如果不是,n自增,再判斷 85 { 86 n++; 87 } 88 } 89 } 90 }