- #1
soandos
- 166
- 0
I realize that this might seems to be a strange question, but after doing some coding i realized the following.
to brute force the factorization of all numbers less than one million takes around 665 million tests (i.e. does this number divide the original).
to do it "smarter" (least i thought) uses a list of the primes, and every time one goes in, it divides the original number by that prime, and tries again. failing that, it goes to the next primes. it stops when the original number is one. the number of tests for this is about 1.398 billion.
first, am i doing something terribly wrong in my implementation of the "smarter" way?
second, is there a better theoretical way to factor numbers given all the primes less than them?
to brute force the factorization of all numbers less than one million takes around 665 million tests (i.e. does this number divide the original).
to do it "smarter" (least i thought) uses a list of the primes, and every time one goes in, it divides the original number by that prime, and tries again. failing that, it goes to the next primes. it stops when the original number is one. the number of tests for this is about 1.398 billion.
first, am i doing something terribly wrong in my implementation of the "smarter" way?
second, is there a better theoretical way to factor numbers given all the primes less than them?