2
\$\begingroup\$

This code is for a problem in which I'm to find the total number of numbers that exist between A and B, of which sum of digits and sum of square of digits are prime.

How can I make this optimal?

import java.util.Scanner;
public class LuckyNumbers {
    static int T,ans[];
    static long A,B;
    public static void main(String ar[]){
        Scanner scan=new Scanner(System.in);
        T=scan.nextInt();
        ans=new int[T];
        for(int i=0;i<T;i++){
            A=scan.nextLong();
            B=scan.nextLong();
            for(long j=A;j<=B;j++){
                if(getLucky(j)){
                    ans[i]++;
                }
            }
        }
        for(int i=0;i<T;i++){
            System.out.println(ans[i]);
        }
    }
    public static boolean getLucky(long j){
        boolean lucky=false;
        long rem,sum=0,sum1=0;
        while(j>0){
            rem=j%10;
            sum=sum+rem;
            sum1=sum1+(rem*rem);
            j=j/10;
        }
        if(isPrime(sum)&&isPrime(sum1)){
            lucky=true;
        }
        return lucky;
    }
    public static boolean isPrime(long sum){
        boolean status=true;
        if(sum!=1){
            for (int i=2; i < sum ;i++ ){
              long n =sum % i;
              if (n==0){
                    status=false;
                    break;
              }
            }
        }else{
            status=false;
        }
        return status;
    }
}
\$\endgroup\$
  • \$\begingroup\$ You need to invest some time in profiling this code (whether by adding your own timers or by leveraging some sort of tools / frameworks / profilers. The run this (or improved) code with increasingly large input and get a sense for what the complexity is. Do try to break things up as much as you can, so that you can experiment with swapping individual pieces in and out. \$\endgroup\$ – Leonid Feb 11 '12 at 19:21
5
\$\begingroup\$

While everybody mentioned optimizing isPrime, nobody spotted the one glaring ineffiency: You can break the loop as soon as i*i > sum. Further you can skip the even divisors except 2:

public static boolean isPrime(long sum){
    if (sum < 2) return false;
    if (sum < 4) return true;
    if (sum % 2 == 0) return false;
    int limit = (int) (Math.sqrt(sum)); 
    for (int i = 3; i <= limit; i += 2 ){
          if (sum % i==0){
               return false;
          }
    }
    return true;
}

Alternatively you can use BigInteger.isProbablePrime(). Despite its name it returns correct results - at least in the long range.

\$\endgroup\$
  • \$\begingroup\$ I was waiting for someone to point that one out. \$\endgroup\$ – Rex Kerr Feb 11 '12 at 19:20
6
\$\begingroup\$

Some thoughts on speed:

  • Start caching results in isPrime.
  • Print things as soon as you calculate them, no need to store them back into an array. (This makes debugging easier, too.)
    • As Leonid pointed out, storing things may be a good idea. I would keep it an array in that case, not a linked list, as that costs less time.
    • However, I would simply disable output when profiling, and keep my suggestion for debugging.
    • On a similar note, consider splitting both the main algorithm and the output into separate functions so that you can easily disable both. That makes it much easier to check how much each stage of the algorithm (parsing, processing, printing) is taking.
  • You could try caching rem*rem, as you know there's only ten possibilities. May be faster, may be slower.
  • You should take a look at the input you'll be dealing with and figure out what values your program needs to have that could be given beforehand. What values can the numbers you're checking for primality be? (I would guess you need up to around 2000, but I'm not sure.)

Some general thoughts:

  • Add some comments. What is a lucky number?
  • Add some blank lines.
  • Rename getLucky to isLucky or checkIsLucky. I'd go for the first, but some people will tell you that functions need a verb other than "is". If Java supports it, you could make it an extension method and then do arr[i].isLucky().
  • Don't make variables static unless they have to be. Both T and ans can be local to main.
  • Make your variable names more meaningful. In particular, replacing T with numberOfInputPairs (or numInputPairs, at least) would improve matters.
  • Don't use the same name for two variables, with one letter difference. Why do you have sum and sum1? What's the difference between them?
  • Use the += operator when possible. sum1 += rem*rem is easier to read than what you have.

To address the question of numberOfInputPairs being too long: let's reformat the code a little and change the name appropriately:

public static void main(String ar[]){
    Scanner scan = new Scanner(System.in);
    int numberOfInputPairs = scan.nextInt();
    int ans[] = new int[numberOfInputPairs];

    for (int i = 0; i < numberOfInputPairs; i++){
        A = scan.nextLong();
        B = scan.nextLong();
        for (long j = A; j <= B; j++) {
            if (getLucky(j)) {
                ans[i]++;
            }
        }
    }

    for (int i = 0; i < numberOfInputPairs; i++) {
        System.out.println(ans[i]);
    }
}

Yes, if no whitespace is added, the longer variable names make a wall of text a bigger wall of text, and convey very little meaning. However, with just a slight increase in the amount of whitespace, I find that the longer variable name is no less clear and makes it clear what is being done.

(By the way, I think this is partially a language problem: as things are, it is used three times, while a proper for-each loop would mean it would only need to be used once.)

I do not agree with n or T offering that clarity; numPairs would do, too, and is down to personal preference.

\$\endgroup\$
  • 1
    \$\begingroup\$ Depending on the problem/algorithm at hand, System.out.println can be the slowest part. When reasoning about / profiling the run time, I would not want to analyze the mix of IO and CPU crunching. I would stick the result into say a LinkedList, and then print it out all at once at the end. \$\endgroup\$ – Leonid Feb 11 '12 at 19:24
  • \$\begingroup\$ Good answer overall, but totalNumberOfInputs? Really? Awfully verbose for something that is arguably misleading--you actually have two inputs for each iteration! nInputPairs or just plain n (or T) would be better. \$\endgroup\$ – Rex Kerr Feb 11 '12 at 19:28
  • \$\begingroup\$ @RexKerr, Leonid: Edited to react to your suggestions, thanks. \$\endgroup\$ – Anton Golov Feb 11 '12 at 21:39
3
\$\begingroup\$

I think you chould consider improving the isPrime(long sum) (i don't think sum is a luckily chosen name here, by the way).

Consider using a better algorythm, e.g. a sieve fo atkin instead of looping all values.

See e.g. this implementation

On this basis you can improve caching on your specific needs.

I would give you the advice to optimize your code for readability and start measuring. Only pull in optimizations that are worth. Don't clutter up your code without value.

\$\endgroup\$
2
\$\begingroup\$

Code optimization can be tricky. Make the code optimal can be something different.

There's a lot of sub-question: Optimization, in term of speed / memory ? On which device? From a fresh start, or after a long running time ?

But first, give variable a explicit name, because A,B,T means nothing to me/ others code, and longer variable name won't slow down your code. Second, use a profiler may help you, I usually use jvisualvm.exe (in the jdk). Third, a faster code on your machine won't necessary be faster on a other computer / device.

In your getLucky method, the lucky variable is not necessary, you could do: return (isPrime(sum)&&isPrime(sum1));

but it will render your code less readable.

In your isPrime method, the for loop check the i is a integer and the sum is a long. So if the sum is bigger than MAX_INTEGER you will be in trouble.

\$\endgroup\$
  • \$\begingroup\$ Algebra does math with one-letter variables all the time. Why does it magically become hard to understand once it's written down as code? And they're being used as limits of an iteration. How is that hard to spot? \$\endgroup\$ – Rex Kerr Feb 11 '12 at 13:00
1
\$\begingroup\$

Not sure about optimisation, but I think readability is really important, and conciseness is a big part of readability. So I would write the isPrime method like this.

public static boolean isPrime(long sum){ 
     if( sum == 1 ){
         return false;
    }
    for( int i = 2; i < sum ;i++ ){ 
        if( sum % i == 0 ){
            return false;
        }
    }
    return true; 
} 

Also, lots of work has been done on good algorithms for testing primality. Running through and testing for divisibility by every integer is far from optimal. So you could do some research on this - it's a mathematics question, not a computer science one.

One idea that you could try is the whole difference of squares thing. If you've got an array in which you've stored lots of square numbers, then you can use this to test with subtraction, rather than division. That is, if you're testing some odd number z, which happens to be x * y, then it's also

((x+y)/2)^2 - ((x-y)/2)^2

And since x and y must both be odd, both of the entities being squared are integers. So looking for two squares that differ by z turns out to be equivalent to looking for factors, but computationally much easier.

Have a try at turning this approach into Java code. Post a comment on this answer if you get stuck, and I'll try to give you some more guidance.

\$\endgroup\$
  • \$\begingroup\$ Factorization is an NP problem, primality testing a P problem (as proven by the AKS theorem), so generally you can say much faster if a number is prime or composite than calculating the actual factors (that's the fact RSA and other encryption methods rely on). Further Wikipedia states for the Fermat factorization you describe "In its simplest form, Fermat's method might be even slower than trial division (worst case)." \$\endgroup\$ – Landei Feb 11 '12 at 22:23
0
\$\begingroup\$

isPrime(long num) method can be improved by using other prime number checking algorithms such as Fermat theoram, reducing check space or by simply incrementing by 2 instead of i++.You don't need to check every even number upto n.Infact, you don't need to check every odd number upto n.just check it upto sqrt(number).

eg ->

      if(num%2==0)
        return false;
      for(i=3;(i*i)<num;i+=2)
      {
       .............
      } 

    onw more 

For more details , refer to 1st chapter of Fundamentals of Algorithms by Sahni

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.