Wie überprüft man, ob eine Zahl in der Form A^B dargestellt werden kann?

Ich wurde kürzlich in einem Interview gebeten, ein Programm zu schreiben, um zu überprüfen, ob eine Nummer in Form von A^B dargestellt werden kann. Ich konnte das Problem nicht lösen, da ich nicht einmal einen richtigen Ansatz hatte, um das Problem zu lösen.Wie überprüft man, ob eine Zahl in der Form A^B dargestellt werden kann?

Hier sind einige Beispiele

Input = 4 
Output = true

Wie es als 2^2

Input = 536870912 
Output = true

dargestellt werden kann, wie es als 2^29

Input = 1024000000 
Output = true

Wie es dargestellt werden kann, kann als 2^16 * 5^6 = 32000^2

dargestellt werden 0

Kann jemand bitte eine Lösung (vorzugsweise mit Java) für dieses Problem bereitstellen?

Quelle

2016-04-24 Nishant123

Hint - Primfaktoren. Jede ganzzahlige Zahl kann durch das Produkt ihrer Primfaktoren dargestellt werden. Die Berechnung der Primfaktoren einer Zahl wird als [Primäre Zerlegung] bezeichnet (http://revisionworld.com/gcse-revision/maths/number-and-algebra/number/numbers)/Primfaktor-Zerlegung). –

Sie können in der ersten die Quadratwurzel der Zahl machen, dann beginnen, die Zahl durch alle Primzahlen zu teilen, die unter der Quadratwurzel liegen, wenn Sie eine Zahl finden, die Sie stoppen, sonst fahren Sie fort, bis Sie 1. –

erreichen keine Beschränkung auf "B", dann sag einfach "wahr" für alles. 'A = A^1' für alle' A'. – user2478398

Wenn Sie eine Antwort für X wollen = A ^B für einen bekannten X, wobei sowohl A ≥ 2 und B ≥ 2 und die beide ganze Zahlen, dann ist die kürzeste Suche tut A = ^B √ X für B = 2..n, bis ein < 2.

public static void findPower(double value) { 
    if (value < 1 || value % 1 != 0) 
     throw new IllegalArgumentException("Invalid input: " + value); 
    boolean found = false; 
    for (int exp = 2; ; exp++) { 
     long base = Math.round(Math.pow(value, 1.0/exp)); 
     if (base < 2) 
      break; 
     if (Math.pow(base, exp) == value) { 
      System.out.printf("%.0f = %d^%d%n", value, base, exp); 
      found = true; 
     } 
    } 
    if (! found) 
     System.out.printf("%.0f has no solution%n", value); 
}

TEST

findPower(4); 
findPower(123_456); 
findPower(536_870_912); 
findPower(1_024_000_000); 
findPower(2_176_782_336d); 
findPower(205_891_132_094_649d);

OUTPUT

4 = 2^2 
123456 has no solution 
536870912 = 2^29 
1024000000 = 32000^2 
2176782336 = 46656^2 
2176782336 = 1296^3 
2176782336 = 216^4 
2176782336 = 36^6 
2176782336 = 6^12 
205891132094649 = 14348907^2 
205891132094649 = 59049^3 
205891132094649 = 729^5 
205891132094649 = 243^6 
205891132094649 = 27^10 
205891132094649 = 9^15 
205891132094649 = 3^30

Quelle

2016-04-24 20:38:12 Andreas

Wie überprüft man, ob eine Zahl in der Form A^B dargestellt werden kann?

Antwort

Verwandte Themen