Printable View
there is a question about making a program to find prime factorization.
And it says : " Your algorithm must be quicker for some types of numbers than for others of similar size"
i dont know what "others of similar size" means.
i guess that kind of numbers : 2^n.
since i set my initial test number t=2
but i cant find those numbers of "similar size"
The algorithm's quicker for numbers that have 2 as the only prime factor; "similar size" may refer to their length ie the no. of digits in 'em.Quote:
Originally Posted by szpengchao
Do you mean having 60 as the input and "2, 2, 3, 5" as the output, reducing a number to prime factors? This shouldn't be too difficult. Start with 2, the lowest possible prime number. If "Input % 2 == 0", then factor 2 out of it. Write the output and divide by 2. If the number still is a multiple of 2, repeat until it is not. If "Input % 2 != 0", then go to the next prime number, 3. Continue in this fashion until you've reached or exceeded the square root of your remainder. Take 127. You can't take any primes out of it, even with something as high as 11, but 13, the next one, is above the square root of this value so you don't need to do 13 and above. This is the way I do it in my head and on paper.
Quote:
Originally Posted by itCbitC
so i guess u mean, the algorithm is quicker for 2^n than other numbers with the same number of digits???
yep!Quote:
Originally Posted by szpengchao