Enjoy an ad free experience by logging in. Not a member yet? Register.

Results 1 to 3 of 3
Thread: count/find Powerful Numbers

02202011, 01:39 PM #1
 Join Date
 Mar 2010
 Posts
 18
 Thanks
 0
 Thanked 0 Times in 0 Posts
count/find Powerful Numbers
Hey guys !
I'm testing my skills with some tests and came upon one issue:
Code:import java.util.*; public class Powers { public static int countPowerfulNumbers(int from, int to) { /* A powerful number is a positive integer m that for every prime number p dividing m, p*p also divides m. (a prime number (or a prime) is a natural number that has exactly two (distinct) natural number divisors, which are 1 and the prime number itself, the first prime numbers are: 2, 3, 5, 7, 11, 13, ...) The first powerful numbers are: 1, 4, 8, 9, 16, 25, 27, 32, 36, ... Please implement this method to return the count of powerful numbers in the range [from..to] inclusively. */ List<Integer> primes = new ArrayList<Integer>(); for(int i = 2; i <= to; i++){ boolean isPrime = true; for(int j = 2; j <= i/2; j++) if(i%j==0) isPrime = false; if(isPrime) primes.add(i); } System.out.println("BEGIN*************PRIMES*************"); System.out.println(primes); System.out.println("END***************PRIMES*************"); for(int p = from; p <= to; p++){ for(int x : primes) if((p%x==0)&&(p%(x*x)==0)){ System.out.println(p); break; } } return primes.size(); } }
The way I thought it :
Find all prime numbers (the range is big,Code:i<to/2 or /4
if (powerN % primeN == 0 && powerN % (primeN*primeN))
then powerCount++, or just add powerN to a list (did that fordebugging purposes).
The problem is that I'm getting more prime numbers that I should. I think I'm doing the wrong approach, but I'm doing exactly what the info tells me to do.
Would be great if you could throw in a few suggestions.
Example: for range (1,150), I should be getting these
1, 4, 8, 9, 16, 25, 27, 32, 36, 49, 64, 72, 81, 100, 108, 121, 125, 128, 144
but instead I get like a hundred.
Thanks!

02202011, 02:24 PM #2
 Join Date
 Dec 2007
 Posts
 6,682
 Thanks
 436
 Thanked 890 Times in 879 Posts
p*p = m => p = sqrt(m) and p is prime. That means you need to count all prime number greater or equal then sqrt(from) and less or equal sqrt(to).
The hardest problem here is to find all prime numbers between that range.
best regards

02202011, 03:16 PM #3
 Join Date
 Mar 2010
 Posts
 18
 Thanks
 0
 Thanked 0 Times in 0 Posts
Thank you for the great hint. I was thinking a half an hour ago that maybe it has smt to do with the sqrt, but I've fixed it with another trick :
So in my program :
Condition 1 : PowerN(inquestion) % prime == 0 && powerN % prime*prime == 0
Condition 2 : The result of powerN % prime*prime == (a previous powerN calculated, or the prime number itself(prime))
I added a condition that the result of PowerN / (prime*prime) must be a powerful number or the primeNumber itself from the current operation.
P*P = m ?
I dunno, the condition is PowerNumber divides primeNumber and primeNumber^2.
Anyway, it's worked now and giving results like good old wikipedia.
Thanks for the help!
I just looked over it and yes sometimes the result(sqrt) is equal to the prime number divided. But it's working well and I'm to laizzy to press on...Last edited by Buzdugan; 02202011 at 03:20 PM.
AdSlot6