Integer factorization given enough primes

[soandos]

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?

 

[soandos]

It also seems that since PrimePi(x) grows faster than Sqrt(x) doing it the "smart" way will continually get worse thant the brute force way.

 

[baric]

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?

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

 

[soandos]

I don't want to know if its prime or not, I want the factorization. If i want to know if its prime, I just have to check my list of primes.

 

[coolul007]

Factorization only needs to be brute force up to the square root of the number.

 

[pwsnafu]

second, is there a better theoretical way to factor numbers given all the primes less than them?

The set of all primes less than a fixed constant is called a factor base. There are a number of factorization methods that use this such as http://en.wikipedia.org/wiki/Dixon%27s_algorithm" , and its optimizations.

 

[soandos]

Thank you, any ideas where there are implementations of it, or should I just write my own?

 

[baric]

Thank you, any ideas where there are implementations of it, or should I just write my own?

I'm guessing you'll have to write your own. The wiki page gives a good example, though, for factoring 84923. Consider yourself lucky! :P

 

[willem2]

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?

Yes, You only need to divide by primes smaller or equal than the square root of the
number you're testing. There are only 168 primes <=1000, so this means less than 168
million tests to factor all the numbers less than 1 million.

If you want to factor ALL the numbers below a million, a variation of th sieve of Eratosthenes will be the fastest. You can mark all numbers divisible by p with p, (so you end up with a list with all the numbers <10^6 with a single prime factor that divides them (if they are not prime). To factor you look up the number in the list, divide by the factor, look up the new number in the list etc.
Of course you will run out of memory around 10^9 .