2
\$\begingroup\$

I want to calculate all the prime factors of a number in the range 2 ≤ N ≤ 107. Here is my function:

public static long cal_me(int a, long[] A){

     long ans=1;
     int count=0;
     while(a%2==0){ 
         a/=2;
       count++;
     }
     if(count!=0)  // I am calculating value which depend on Number of prime Number
     ans = (long) ((Math.pow(2,2*count+1)+1)/3);


     if(A[a]!=-1) return ans*A[a];

     for(int i=3;i<=Math.sqrt(a) && a!=1;i+=2)
     {
         if(A[a]!=-1){ 

             return ans*A[a];
         }
         count=0;
           while(a%i==0){ 
               a/=i;
               count++;

           }



           if(count!=0)
               ans *=(long) ((Math.pow(i,2*count+1)+1)/(i+1));



     }

     if(a>2)
        ans *=  (long) ((Math.pow(a,3)+1)/(a+1));

     return ans;
}

My calling function:

for(int i=2;i<=10000000;i++)
A[i] = cal_me(i,A);

The above program me took 10s. I want something faster — how should I improve this?

\$\endgroup\$
  • 3
    \$\begingroup\$ generating a prime-table up to a specific number is pretty costly. Generate the table once at the start before calculating the factors for all numbers instead of generating them it for each number separately. That saves you a lot of unnecessary overhead. \$\endgroup\$ – Paul Nov 13 '15 at 11:19
  • \$\begingroup\$ How is A supposed to be initialized? How are the outputs supposed to be interpreted? \$\endgroup\$ – 200_success Nov 14 '15 at 8:10
2
\$\begingroup\$

Quick observation: you use Math.pow() to calculate powers of two. This is highly inefficient, use bit shifting to prevent long -> double conversion

For example, 2^10 can be calculated very quicky as 1 << 10. See for example here (https://stackoverflow.com/q/141525/461499)

Also you divide a double by a long and then convert to long (in effect flooring), you can skip conversion to double entirely to speed things up.

|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

Yes, you can improve your algorithm if you know that primes are in the form 6k ± 1, with the exception of 2 and 3. So, first you can test if input is divisible by 2 or 3. Then, check all the numbers of form 6k ± 1 ≤ √input.

bool IsPrime(int input)
        {
            //2 and 3 are primes
            if (input == 2 || input == 3)
                return true; 
            else if (input % 2 == 0 || input % 3 == 0)
                return false;     //Is divisible by 2 or 3?
            else
            {
                for (int i = 5; i * i <= input; i += 6)
                {
                    if (input % i == 0 || input % (i + 2) == 0)
                        return false;
                }
                return true;
            }
        }
|improve this answer|||||
\$\endgroup\$

Your Answer

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