Efficient algorithm for finding factors of a number?

Question

I am practicing with programming by doing problems on a site called Project Euler. I understand the logic behind my brute-force approach, but can't figure out a way to make it faster.

I'll leave the details of the problem out of this question, as I don't have trouble with those. Here is my method for finding factors (both prime and composite) of a given number:

public static int countFactors(long n)
{
int count = 0;
for (long i = 1; i <= n; i++)
{
if (n % i == 0)
count++;

}
return count;
}

For example, for n = 28, countFactors(28) will return 6, because the factors of 28 are {1, 2, 4, 7, 14, 28}.

This works fine for smaller numbers, but in my case I need to scan hundreds of thousands of numbers bigger than 200,000,000,000 (which is why I'm using longs). I think I understand the problem: I'm scanning every number from 1->n, which for large values is a very big amount of numbers to scan. This makes my program run significantly slower. How can I modify countFactors() to be more efficient?

Answer 1

Thats just the problem, the more you have to do, the longer it will take, you'll have to live with it... thats why we have loading screens!



although from your code, it looks like your using C#! (public static int...)



you could speed this algorithm up by compiling it with C or C++ ;)

Answer 2

"This works fine for smaller numbers"



Thats just it. As n increases so the number of factors.



There isn't some magical equation that can produce all the factors of some number n. If there was, a lot of things would change. An example is that of RSA encryption which is based on the difficulty of factoring very large numbers (like your 200,000,000,000, and much bigger than that actually).



For this given algorithm, you could look for a recursive function



void factors(long n,long f=1)

{

if(n%f==0)

cout<


if(f==n)

return;



factors(n,f+1);

}



function calls : factors(n)

Answer 3

I'm not sure if there is a simpler way.



"Many cryptographic protocols are based on the difficulty of factoring large composite integers or a related problem, the RSA problem. An algorithm which efficiently factors an arbitrary integer would render RSA-based public-key cryptography insecure."