Count the number of ways an integer can be represented as a sum of consecutive positive integers I am trying to count the number of ways an integer can be represented as sum of 2 or more consecutive positive integers.  My Code is working in under 1 second for small inputs (\$\le 10^7\$) but after that it's taking too long. How can I lower the time complexity of the solution?

import java.io.*;

//sum needs to contain atleast 2 elements
public class IntegerRepresentedAsSumOfConsecutivePositiveIntegers
{
    public static long count = 0;
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long num = Long.parseLong(br.readLine()); //Enter a number( &lt;=10^12)
        //driver(num);
        func(num);
        System.out.println("count = " + count);
    }


    public static void func(long num)
    {
        long temp,i,j;
        long limit = (num / 2);
        for(i = 1 ; i &lt;= limit ; i++)
        {
            temp = num;
            j = i;
            while(j &lt; temp)
            {
                temp = temp - j;
                j++;
            }
            if(j == temp)
            {
                count++;
            }
        }
    }

}
Some ideas that can improve the complexity:


I am seeing that you are trying to equate num to i + (i+1) + ... + j, you can calculate this by j*(j+1)/2 - i*(i-1)/2
Further for a given i if we assume that num = j*(j+1)/2 - i*(i+1)/2 we can solve the quadratic equation and check if we get integral roots, that makes the whole solution O(n)
You may also wanna try looking up solutions to quadratic Diophantine equations, see here, after all j*(j+1)/2 - i*(i-1)/2 = num is a quadratic diophantine equation only. 


What I would probably do

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class ConsSum {

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long num = Long.parseLong(br.readLine());
        System.out.println("There are " + getConsSumWays(num) + " total way(s) to get " + num);
    }

    private static int getConsSumWays(long n) {
        int count = 0;
        /*
         * i + (i+1) + (i+2) + ... + j = n
         * =&gt; j(j+1)-i(i-1)=2n
         * =&gt; let k = j(j+1) = 2n + i(i-1)
         */
        for (long i = 0; i &lt;= n / 2; i++) {
            long k = 2 * n + i * (i - 1);
            /*
             * j^2+j-k=0 =&gt; j = [-1+sqrt(1+4k)]/2 since j&gt;0
             */
            long j = (long) ((-1 + Math.sqrt(1 + 4 * k)) / 2);
            if (j * (j + 1) == k) {
                System.out.println("sum [" + i + ".." + j + "] = " + n);
                count++;
            }
        }
        return count;
    }

}