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();
}
}

As you can see, at first I'm getting the primes. This version of the code skips 1, but if i starts from 1 it will have it, the consequence beeing that the powerful numbers resulting will be many in numbers.

The way I thought it :

Find all prime numbers (the range is big, would have been enough), and now for each integer from "FROM" to "TO" check to see if there is a matching INTEGER from PRIMES that divides it at ^1 and at ^2

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!