0%

算法题：质数的幂次方

Posted on Edited on In Valine:

前几天做的牛客网全国统一校招的笔试题里的一道算法题
题目大意是给定一个数，判断此数是否为一个质数的整数次幂，如：
27 = 3^3 则输出3 ，3 否则输出not found
以下为我的解答，只是大概思路，真正遇到这类题肯定要再优化算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Test {
        public static void main(String[] args) {
            int a = 27;
            int b = 0;
            for (int i = 2; i <= 100; i++) {
                for (int j = 2; j <= i; j++) {
                    if (i%j==0&&i!=j) {
                        break;
                    }
                    if(i%j==0&&i==j){
                        for ( b = 0; b <= 100; b++) {
                            if (Math.pow(i , b)==a) {
                                System.out.println(i+" and "+b);
                                return;
                            } 
                        }
                    }
                }if (i==100&&Math.pow(i , b)!=a) {
                    System.out.print("no");
                }
            }
        }
    }