超级素数幂

[编程题]超级素数幂

热度指数：3945 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

如果一个数字能表示为p^q(^表示幂运算)且p为一个素数,q为大于1的正整数就称这个数叫做超级素数幂。现在给出一个正整数n,如果n是一个超级素数幂需要找出对应的p,q。

输入描述:

输入一个正整数n(2 ≤ n ≤ 10^18)

输出描述:

如果n是一个超级素数幂则输出p,q,以空格分隔,行末无空格。 如果n不是超级素数幂，则输出No

示例1

输入

输出

3 3

算法知识视频讲解

Java

小风筝0010

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //int最大范围为2^32.远远小于10^18.故用long.long的范围为2^64
        long num = sc.nextLong();
        double p;
        boolean flag = false;
        for (long q = 2; q * q <= num; q ++) {
            p = Math.pow((double) num, 1d/q);
            //(long)p == p 判断p经过 Math.pow((double) num, 1d/q)后是否为整数
            if ((long)p == p && isPrimeNumber((long) p)) {
                System.out.println((long) p + " " + q);
                flag = true;
                break;
            }
        }
        if (!flag) {
            System.out.println("No");
        }
    }

    /**
     * 判断是否为素数
     * @param n 输入long值
     * @return true素数 false 不是素数
     */
    public static boolean isPrimeNumber(long n) {
        if (n <= 1) return false;
        for (int i = 2; i * i <= n; i ++) {
            if (n % i == 0) return false;
        }
        return true;
    }
}

编辑于 2017-03-12 16:24:56 回复(6)

Java

Stack

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long input = sc.nextLong();
        int q = 2;
        double p;

        do {
            p = Math.pow(input, 1.0 / q);
            if (Double.compare(p, Math.floor(p)) == 0 && isPrime((int) p)) { // p为整数且为素数
                break;
            }
            q++;
        } while (p >= 2);

        if (p < 2) {
            System.out.println("No");
        } else {
            System.out.println((int)p + " " + q);
        }
    }

    private static boolean isPrime(int p) {
        if (p < 2) return false;

        double sqrt = Math.sqrt(p);
        for (int i = 2; i <= sqrt; i++) {
            if (p % i == 0) {
                return false;
            }
        }
        return true;
    }

}

编辑于 2017-03-08 09:22:42 回复(2)