How to print an arraylist such that it is the power of all the prime numbers with an upperbound

user_18421909 0
Viewed 116

I want to get an arraylist of all the numbers that are powers of primes below or equal to the upperbound.

this is what I got:

public class PrimePowers {
public static void main(String[] args) {
    System.out.println(getPrimePowers(10));
}

public static List<Integer> getPrimePowers(int upperBound) {
ArrayList<Integer> primePower = new ArrayList<>();
for (int flag = 2; flag <= upperBound; flag++){

}

    return ;
}
public static List<Integer> getPrimeNumbers(int upperBound){
    ArrayList<Integer> primeNumber = new ArrayList<>();
    for (int i = 2; i <=upperBound; i++){
        if (!isPrime(i)) {
            if(i != 1) {
                primeNumber.add(i);
            }
        }
    }
    return primeNumber;

}
public static boolean isPrime(int num){
    boolean flag = false;
    for (int i = 2; i <= num / 2; ++i) {
        // condition for nonPrime number
        if (num % i == 0) {
            flag = true;
            break;
        }
    }

    return flag;
}
}

so I have all the primenumbers, now I have to get all their powers below the upperbound. my first question: how do I get all their powers, without getting 2 of the same in the list? or is that not an issue? my second question: how do I program it such that I can get the power to also keep continuing going up, until the upper bound? i.e. if the upper bound is 10, with prime number 2 I should get 2^2 = 4 and 2^3 = 8.

an example: program is called as getPrimePowers(50) return: [4, 8, 9, 16, 25, 27, 32, 49]

sorry if this is really confusion, but I really appreciate the help

primes for-loop java
2 Answers

You can use IntStream:

  • Create an IntStream with values between 2 and the square root of the upper bound.
  • Filter the stream prime numbers.
  • Flat map the stream for the powers using an IntStream mapper, map it to the power and filter values that are lower than the upper bound.
  • Finally, sort the resulting stream and collect it to a List.

Summaraizing in a method:

public static List<Integer> primePower(int upperBound) {
    return IntStream.rangeClosed(2, (int) Math.sqrt(upperBound))
            .filter(i -> isPrime(i))
            .flatMap(i -> IntStream.rangeClosed(2, 
                        (int) Math.rint(Math.pow(upperBound, 1d / i)))
                    .map(j -> (int) Math.pow(i, j))
                    .filter(j -> j <= upperBound))
            .distinct().sorted()
            .boxed().toList();
}
    
private static boolean isPrime(int value) {
    return IntStream.rangeClosed(2, (int) Math.sqrt(value))
      .allMatch(i -> value % i != 0);
}

Test:

List<Integer> primePower = primePower(50);

System.out.println(primePower);

Output:

[4, 8, 9, 16, 25, 27, 32, 49]
user_102436340

First, to calculate all the primes that are smaller then the upper bound, use isProbablePrime, which is way faster than any implementation you will write.

Secondly, after you collected all the primes, for each one of them you can calculate all their power by:

prime = ...
int max_power = (int)Math.floor(Math.log(upperBound) / Math.log(prime));
for (int p = 1, val = 1; p <= max_power; p++)
    result.add(val *= prime);

Thirdly, you can't get any duplication (except the number 1), because each number can be factorized into primes in exactly one way, so don't worry about it.

user_64170570
Related