Geek asks and answers

Sort numbers having 4 Divisors (java)

I need to sort a range of numbers. Numbers can be from 0 to 1000. The user enters a range of numbers from 0 to 1000. Therefore, if they, for example, can be entered 0 → 500.

My goal would be to take all numbers in a given range and print all numbers in that range that have only 4 possible divisors (including 1 and yourself.

I am wondering if I should use an algorithm like this , or if I have to check the int array containing all numbers from 1 to 1000, which are divisible by 4 (so that the array does not have 1-1000, it has numbers in this range which will be shared only 4 times). Manual work is required to add all possible divisors to this array).

I am looking to make it efficient, I am not sure if such an algorithm would be very fast for this.

+3
source share
1 answer

You are looking for a number that will produce the product of two primes: or a cube of a prime. Since your numbers are small, you can simply make a short table of primes from 2 to 500. Then, starting at 2, multiply each number by each of the primes above it until you exceed the upper limit.

Edit: Is this homework? If so, I probably already said too much. If this is not the case, I can provide some code or pseudo-code if my answer does not make sense.

: , : . . ( , , .)

:

for ( p1 is a prime in your list, except for the last) {
    if p1 cubed is in your range, add it to the answer
    for (p2 is a prime in your list greater than p1) {
        if p2*p1 is in your range, add it to the answer
        //optimization: break when you know you won't find any more
    }
}
// optimization: calculate the ranges of p1 and p2 to be included 
// before you start each loop
// (probably only worthwhile if you raise the limit to something 
// much larger than 1000)

, , . ( 292 0 1000. --- 95 .)

+6

More articles:


All Articles