Hello and welcome to our community! Is this your first visit?
Register
Enjoy an ad free experience by logging in. Not a member yet? Register.
Results 1 to 3 of 3
  1. #1
    New Coder
    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();
        }
    }
    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,
    Code:
    i<to/2 or /4
    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!

  • #2
    Master Coder
    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

  • #3
    New Coder
    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; 02-20-2011 at 04:20 PM.


  •  

    Posting Permissions

    • You may not post new threads
    • You may not post replies
    • You may not post attachments
    • You may not edit your posts
    •