首页 > 试题广场 >

超级素数幂

[编程题]超级素数幂

热度指数：3943 时间限制：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

算法知识视频讲解

C/C++

路过的熊

#include<iostream>
#include<cmath>
using namespace std;
bool isprime(int n){
	int s = sqrt(n);
	for (int i = 2; i <= s; i++)
	if (n % i == 0)
		return false;
	return true;
}
int main(){
	long long int n;
	while (cin >> n){
		int p, q;
		int ceil = log10(n) / log10(2);
		for (q = 2; q <= ceil; q++){
			p = pow(n, 1.0 / q);
			//double转换为int会丢失，所以下面要再次判断
			if (pow(p, q) == n && isprime(p)){
				cout << p << " " << q;
				break;
			}
		}
		if (q > ceil)
			cout << "No";
	}
	return 0;
}
//时间复杂度O（log2(N) * sqrt(sqrt(N))），也就是 以2为底N的对数 乘以 N的4分之1次方

编辑于 2017-03-10 18:33:41 回复(7)

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)

天祺

import java.util.Scanner;

public class Main{

public static void main(String[] args) {
    Scanner scanner=new Scanner(System.in);

    long num=scanner.nextLong();
    int end=(int) Math.sqrt(num);
    for(int i=2;i<=end+1;i++){
        double tem=Math.pow(num, (double)1/i);
        if(tem==(long)tem&&isPrimeNum((long) tem)){
            System.out.println((long)tem+" "+i);
            break;
        }
        if(i==end+1)System.out.println("No");
    }
    scanner.close();
}

public static boolean isPrimeNum(long num){
    if(num<=1)return false;
    for(int i=2;i*i<=num;i++){
        if(num%i==0)return false;
    }
    return true;
}

}

发表于 2017-04-02 10:52:19 回复(0)

Drink.C

import sys
import math

def isI(q):
    i=2
    while i<int(math.sqrt(q))+1:
        if q%i==0:
                return False
        i+=1
    return True

n=sys.stdin.readline()
n=int(n)
flag=True
for i in range(2,60):
    q=math.pow(n,1.0/i)
    if q % 1 == 0:
        if isI(q):
            flag=False
            print int(q),i
            break
if flag:

    print 'No'

发表于 2017-03-22 16:58:00 回复(0)

C/C++

BenBenBenBenBen

#include <iostream>
#include <cmath>
using namespace std;

/*素数判定函数*/
bool isPrime( int n ){
    if( n <= 1 ){
        return false;
    }
    for( int i = 2; i <= sqrt(n); ++i ){
        if( n%i == 0 ){
            return false;
        }
    }
    return true;
}

int main()
{
    long long int n;
    while( cin>>n ){
        int max_q = log2(n);
        int flag = 0;
        for( int q = 2; q <= max_q; ++q ){
            double p = pow( n, 1.0/q );//p^q = n  ——>  p = n^(1/q)
            if( p-int(p)==0 && isPrime( int(p) ) ){//p^q = n  ——>  n开q次方后恰好得到整数p
                cout<<int(p)<<" "<<q<<endl;
                flag = 1;
                break;
            }
        }
        if( !flag ){//未找到满足条件的p,q
            cout<<"No"<<endl;
        }
    }
    return 0;
}

发表于 2017-03-15 09:51:39 回复(2)

繁星2012

#include <iostream>
#include <math.h>
#include <vector>


using namespace std;

double sushu(long long n)
{
	for (long long i=2; i<=sqrt((double) n); ++i)
	{
		if (n%i == 0)
		{
			return 0;
		}
		
	}

	return 1;
}

int main(){


	long long n, nCurrent;

	double i=2;
	int flag = 0;
	cin>>n;

	do 
	{
		nCurrent = ceil(pow((double)n,(double)(1.0/i)));
		if (sushu(nCurrent) && (pow(nCurrent, i) == n))
		{
			flag = 1;
			break;
		}
		i++;


	} while (nCurrent>2);


	if (flag)
	{
		cout<<nCurrent<<" "<<i<<endl;
	}
	else
	{
		cout<<"No"<<endl;
	}


	return 0;
}

发表于 2017-03-08 10:05:22 回复(0)

SuperK

来个javascript版的

var rl = require("readline").createInterface(process.stdin, process.stdout);

var args = [];

rl.on('line', function(data){

args.push(data);

rl.close();

});

rl.on('close', function(){

var num = args[0];

var p,q;

/* 暴力的做法，分别循环处理p和q，但是编译器无法通过

if(num>2){

var sum = 0;

for(p=2;p<Math.sqrt(num);p++){

if(isPrime(p)){

for(q=2;q<Math.sqrt(num);q++){

if(Math.pow(p,q)==num){

sum+=1;

console.log(p+" "+q);

break;

}

if(sum==0){

console.log("No");

}*/

//方法二：从q到p的映射关系

var maxq = Math.log(num)/Math.log(2);//N=p的q次方，显然p最小时q最大，因为最小的素数是2，所以q的上限也就是log2N

for(q=2;q<=maxq;q++){

p=Math.pow(num,1/q);

if((p-parseInt(p)==0)&&Math.pow(p,q)==num&&isPrime(p)){

console.log(p+" "+q);

break;

}

if(q>maxq){

console.log("No");

}

});

//首先是搞清楚如果判断一个数为素数

function isPrime(num){

var n = Math.sqrt(num); //求平方根；

for(var i=2;i<=n;i++){

if(num%i==0){

return false;

}

return true;

发表于 2017-03-10 17:54:20 回复(0)

偶尔刷刷题~

import java.util.Scanner;

public class IsSuperPrime {
	public static boolean isPrime(double i)
	{
		boolean isPrime = true;
		for (int k = 2; k<=Math.sqrt(i); k++)
		{
			if (i%k==0)
			{
				isPrime = false;
				break;
			}
		}
		return isPrime;
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner in = new Scanner(System.in);
		long number = in.nextLong();
		boolean IsSuperPrime = false;
	    long datamax = (long)Math.pow(10, 18);
    	if ((number>=2)&&(number<=datamax))
    	{
		int q = 2;
		double p;
		do
		{
			p =(int)(Math.pow(number, (1.0/q))+0.5);
			if(number==Math.pow(p,q))
			{
				IsSuperPrime = isPrime(p);
				
				if(IsSuperPrime)
				{
					System.out.println((int)p+" "+(int)q);
					break;
				}
			}
			q++;
		}while(p>=2);
		
		if(!IsSuperPrime)
		{
			System.out.println("No");
		}

    	}
    	else
    	{
    		System.out.println("请输入一个2~10^18之间的数");
    	}

	}

}

发表于 2017-03-08 15:14:45 回复(5)

逗比请来的猴子

import java.util.Scanner;

/*
 * 参考大神的解题思路：https://blog.csdn.net/zjkc050818/article/details/65935032
 *
 * 求解p^q =n,其中p为素数，由于范围太大，直接枚举素数效率太低，因此考虑枚举幂指数然后判断相应的p是否为素数
 * */
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            long n = scanner.nextLong();
//            幂指数的范围为(2，log2(n))，log2(n)<=sqrt(n)
            boolean finished = false;
            for (long i = 2; i * i <= n; i++) {
                long tmp = (long) Math.pow(n, 1.0 / i);
                if (Math.pow(tmp,i) == n && isPrime(tmp)) {
                    System.out.println((int) tmp + " " + i);
                    finished = true;
                    break;
                }
            }
            if (!finished) {
                System.out.println("No");
            }
        }
    }

    private static boolean isPrime(long p) {
        for (long i = 2; i <= Math.sqrt(p); i++) {
            if (p % i == 0) {
                return false;
            }
        }
        return true;
    }
}

发表于 2018-04-15 19:06:08 回复(0)

lqqqdu

import java.util.Scanner;

public class Main{

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long n = scanner.nextLong();
        double p;
        int q;
        int flag = 1;
        for(q = 2;q * q <= n;q++){
            p = Math.pow(n, 1.0/q);    //抄的高票答案，关键在于Math.pow()的运用
//和p的表示
            if((int) p == p){
                if(isPrime((int)p) == true){
                    System.out.println((int)p + " " + q);
                    flag = 1;
                    break;
                }
            }
        }
        if(flag == 0){
            System.out.println("No");
        }
    }
    
    public static boolean isPrime(int p){
        
        if(p <= 1){
            return false;
        }
        for(int i = 2;i * i <= p;i++){
            if(p % i == 0){
                return false;
            }
        }
        return true;
    }

}

发表于 2017-12-18 16:57:33 回复(0)

小河沟大河沟

#include<iostream>
#include <cmath>
using namespace std;

bool isprime(long long N)
{
	for (long long i = 2; i <= sqrt(N);i=i+1)  //处理这里的条件啊！！！本来想偶数跳过的
	{
		if (N%i==0)
		{
			return false;
		}
	}
	return true;
}


long long Get_basep_q(long long p,long long q)  //求p的q次幂,直接用pow，AC不过
{
	long long ret = 1;
	long long temp = p;
	while (q)
	{
		if (q%2==1)  //q为偶数最后进判断，q为奇数
		{
			ret *= temp;
		}
		temp = temp*temp;
		q /= 2;
	}
	return ret;
}

//p的q次幂
int main()
{
	long long N;
	while (cin>>N)
	{
		long long maxq = log10(N) / log10(2);
		bool flag = false;
		for (long long i = 2; i <= maxq;i++)
		{
			long long basep = pow(N,1.0/i); 
			if (isprime(basep))
			{
				long long sum =Get_basep_q(basep,i);
				if (sum==N)
				{
					cout << basep << ' ' << i;
					flag = true;
					break;
				}
			}
		}
		if (flag==false)
		{
			cout << "No" << endl;
		}
	}
}

发表于 2017-05-27 11:17:51 回复(0)

Jimmy_gg

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

bool isPrime(int n) {
	if (n < 2)
		return false;
	for (int i = 2; i <= (int)sqrt((double)n); i++) {
		if (n % i == 0)
			return false;
	}
	return true;
}
int main()
{
	using namespace std;
	long long n;
	while (cin >> n) {
		double temp;
		int num = 0;
		int q = 0;
		int i = 2;
		while (1) {
			temp = pow(n, 1.0 / i);
			if (temp == (int)temp) {
				num = (int)temp;
				q = i;
			}
			else if (temp < 2) {
				break;
			}
			i++;
		}
		if (!num) {
			cout << "No" << endl;
			continue;
		}
		else {
			if(isPrime(num))
				cout << num << " " << q << endl;
			else
				cout << "No" << endl;
		}
	}
	return 0;
}

发表于 2017-04-21 10:37:48 回复(0)

蘅芜君

#include<iostream>
#include<math.h> 
using namespace std;
 
bool check(int p) {
    for (int j = 2; j <= sqrt(p); j++)//<=, 等号不能落下
    	if (p % j == 0)		return false;
    return true;
}
 
int main() {
    long long n;
    cin >> n;
    if (n <= 3) {
        cout << "No" << endl;
        return 0;
    }    
	for(int q = 2; q <= log10(n) / log10(2); q++){
        int p = (int)pow((double)n, 1.0 / (double)q);
		if (check(p) && (pow((double)p, (double)q) == n)) {
			cout << p << " " << q << endl;
			return 0;
		}
	}    
    cout << "No" << endl;
    return 0;
}

发表于 2017-04-06 16:58:12 回复(0)

zero_python

'''
总的来说, 求p^q == n, 有两种思路:
第一种: 以p循环, 2 <= p <= sqrt(n), 然后不需要判断p是不是素数. 
第二种: 以q循环, 2 <= q <= log2(n), 需要判断p是不是素数
时间复杂度:
第一种: o(sqrt(n))
第二种: o(log2(n) * n^(1/2q)) 约等于 o(logn * n^0.25) 

用python编写, 第一种会运行超时. 
'''
import math
def is_prime(x):
    for i in range(2, int(math.sqrt(x))+1):
        if x % i == 0:
            return False
    return True

while True:
    try:
        num = int(raw_input().strip())
        if num<=3:
            print 'No'
        for q in range(2, int(math.log(num, 2))+1):
            p = num**(1.0/q)
            if p.is_integer() or round(p)**q == num:
                if is_prime(p):
                    print "{} {}".format(int(p), q)
                    break
        else:
            print 'No'
            
    except:
        break

发表于 2017-03-25 12:04:46 回复(0)

jneeyou

#include <iostream>
#include <cmath>
using namespace std;

bool isPrime(int val){
    if( val == 2) return true;
    if( val % 2 == 0) return false;
    
    int end = sqrt(val);
    for(int i = 3; i <= end; i += 2){
        if(val % i == 0){
            return false;
        }
    }
    return true;
}


int main(){
    long long n;
    int p,q;

    cin>>n;
    int end = log2(n);
    for(q = 2; q <= end; q++){
        p = pow(n, 1.0/q);//n的1/q次方，对n开q次方得到p;(p^q == n)
        if(isPrime(p) && pow(p,q) == n){//p为素数且p^q == n
            cout << p << " " << q;
            break;
        }
    }
    
    if( q > end){
        cout << "No";
    }
}

发表于 2017-03-22 17:38:10 回复(0)

江楼月


	#include <iostream>



	#include <cmath>



	 



	using namespace std;



	 



	bool su(longlongx){



	    longlongn= sqrt((double)x);



	    for(inti=2;i<=n;i++){



	        if(x%i==0)



	            returnfalse;



	    }



	    returntrue;



	}



	 



	intmain(){



	    longlonga;



	    longlongb;



	    cin>>a;



	    for(inti=2;i<=sqrt((double)a);i++){



	        b = pow(a,1.0/(double)i); 



	        if((a-pow(b,(double)i))==0&& su(b)){



	            cout<<b<<" "<<i<<endl;



	            return0;



	        }



	    }



	    printf("No\n");



	    return0;



	}

发表于 2017-03-18 22:35:08 回复(0)

温文吻问

import java.util.Scanner;
public class SuperPrimeNumber {
	public static void main(String[] args){
		Scanner in= new Scanner(System.in);
		int n=in.nextInt(),sum=0,k=0;
		for(int i=2;i<n;i++){
			if(isPrime(i)){
				sum++;
				int j=0;
				while(Math.pow(i, j)<=n){
					j++;
					if(Math.pow(i, j)==n){
						System.out.println(i+" "+j);
						break;
					}
					else if(Math.pow(i, j)>n)
						k++;
				}
			}
		}
		if(sum==k) System.out.println("No");
	}
	public static boolean isPrime(int num){
		boolean flag =true;
		for(int i=2;i<=Math.sqrt(num);i++){
			System.out.println(i);
			if(num%i==0){
				flag=false;
			}
		}
		return flag;
	}
}

/*您的代码已保存

请检查是否存在数组越界等非法访问情况

case通过率为40.00%

自己测试都通过了，不知道是什么问题，求解*/

发表于 2017-03-15 21:25:24 回复(2)

C/C++

BangGui02

#include <iostream>

#include <cmath>

#include <string>

#include <fstream>

#include <algorithm>

using namespace std;

bool isPrimer(long long p)

{

//判断素数

for (long long i = 2; i <= sqrt(p); ++ i)

{

if (p % i == 0)

return false;

}

return true;

}

long long PowerBaseP(long long p, long long q)

{

long long result = 1;

for (long long i = 0; i < q; ++ i)

{

result *= p;

}

return result;

}

int main()

{

long long n;

while (cin >> n)

{

//以2为底，取得最大次数幂

long long ceil = log10(n) / log10(2);

long long q = 2;

long long p = 0;

for (; q <= ceil; ++ q)

{

//根据幂的次数，可以求得p

p = pow(n, 1.0 / q);

//判断p是否为素数，如果是则判断p^q是否等于n

if (isPrimer(p) && PowerBaseP(p, q) == n)

{

break;

}

if (q > ceil)

cout << "No" << endl;

else

cout << p << " " << q << endl;

}

return 0;

}

发表于 2017-03-15 10:56:35 回复(0)

李志2017

package sushu;

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


public class Sushu { 
	


public static void main(String[] args) { 



Scanner sc = new Scanner(System.in); 
int n = sc.nextInt(); 


 if(n>2){
	 int sum=0;
	 
    for (int p=2;p<=Math.sqrt(n);p++){
        if(isPrime( p)){
            for(int q=2;q<=Math.sqrt(n);q++){
                if (Math.pow(p, q)==n){
                    sum+=1;
                    System.out.println(p+" "+q);
                    break;
                    
                }
                
                
        }
            
            
    }

        
    }if(sum==0)

    System.out.println("No ");
       
 }
} 
static boolean isPrime(int p){
	boolean b= true;
	for(int k=2;k<=p/2;k++){
		if(p%k==0){
			b=false;
			break;
			
		}
		
	}
	return b;
}

}

时间复杂度太大了，怎么办

发表于 2017-03-09 20:47:57 回复(0)

C/C++

你好哇

#include<iostream>
#include<cmath>
using namespace std;
bool sushu(long long m)
{
	double  m2 = sqrt(m);
	for (int i = 2; i <= m2; i++)
	{
		if (m%i == 0)
			return false;
	}
	return true;
}

int main()
{
	int p, q, flag ,cnt;
	long long  n,n2;
	while (cin >> n)
	{
		flag = 0;
		double nn = sqrt(n);
		double nn1 = log2(n);
		for (p = 2; p <= nn; p++)
		{
			if (flag == 1)
				break;
			if (sushu(p))
			{   
				cnt = 0;
				n2 = n;
				while (n2%p == 0)
				{	
					n2 = n2 / p;
					cnt++;
				}
				if (n2 == 1 && cnt !=1)
					flag = 1;
			}
		}

		if (flag == 1)
		{
			cout << p-1 << " " << cnt << endl;
		}
		else
			cout << "No" << endl;
	}
	//system("pause");
	return 0;
}
//自我感觉运算速度很快，可是为什么在牛客上编译不过去呢？

编辑于 2017-03-08 18:20:10 回复(0)