is there any fastest algorithm to find factors of given number?

Question

0.00/5 (No votes)

See more:

is there any fastest algorithm to find factors of given number?
in the range of 10^9...
less than O(n)
for(i=2;i<=n/2;i++)
{
if(n%i==0)
printf(i);
}

Posted 5-Oct-13 7:01am

vjnan

Add a Solution

Comments

PIEBALDconsult 5-Oct-13 13:24pm

You only need to go as far as the square root. Also, other than the square root, when you find one you've found two, so print both.

Vivek_Maruxxxx 16-Oct-13 7:17am

its not the right way to do that.

3 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Mehdi Gholam · Accepted Answer · 2013-10-05T07:17:00

Solution 1

Start here : http://en.wikipedia.org/wiki/Integer_factorization[^]

Posted 5-Oct-13 7:17am

Mehdi Gholam

CPallini · Accepted Answer · 2013-10-05T07:41:00

Solution 2

You could, for instance, iterate over a sequence of pre-computed prime numbers.

Posted 5-Oct-13 7:41am

CPallini

Comments

PIEBALDconsult 5-Oct-13 13:52pm

I assume he wants all factors; not just the prime factors.

CPallini 5-Oct-13 15:09pm

Well, all factors are prime numbers...

PIEBALDconsult 5-Oct-13 18:06pm

Are they?

Andreas Gieriet 5-Oct-13 20:35pm

When talking about factorization you usually assume prime factorization, since this is the hard problem. Once you have all prime factors, you can produce all the other (not prime) factors by do all permutations of the prime factors.
Cheers
Andi

PIEBALDconsult 6-Oct-13 1:00am

Yet the code he presented finds all.

" you usually assume prime factorization"

No I don't.

CPallini 6-Oct-13 9:24am

http://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic

Captain Price 6-Oct-13 1:31am

oh, i think they are not !

Andreas Gieriet · Accepted Answer · 2013-10-06T01:31:00

How to know what "fastest" mean?
(a) fastest to execute in production mode
(b) fastest to prepare data (e.g. calculate a lookup table)
(c) fastest to develop

Assuming you aim for (a) and that you can spend any amount of time to develop it (i.e. (b) and (c)) and assuming you have sufficient storage space with adequate access speed, I would go for
1) during development, produce a lookup table for all 10^9 numbers ;-)
1.1) calculate all prime factors for a given number
1.2) produce all combinations of the prime factors to produce all factors
2) in the production, use that lookup table

E.g. for n = 63
1) prime factors: 3 x 3 x 7
2) combinations:

(3) x (3) x (7) = 3 x 3 x 7
(3  x  3) x (7) = 9 x 7
(3) x (3  x  7) = 3 x 21

Now you can think of space optimizations, but this will always go on the cost of execution speed. E.g. move 1.2 to production mode, or compress the table (arrange the table as a tree or partition and compress and only deflate the needed part, etc.), ...

Cheers
Andi