ansaurus

Question

For a given number N i have to find all the prime numbers it's consisting of

Answer 1

+3 A:

The most straightforward way is trial division. Basically just try dividing n by each prime number up to sqrt(n). For large numbers, this is a very slow algorithm.

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

For more sophisticated algorithms, try http://en.wikipedia.org/wiki/Integer_factorization

Joel 2010-02-19 21:03:00

"For large numbers, this is a very slow algorithm". Technically, for numbers with large prime factors this is a very slow algorithm. Since he wants the full factorization, the natural thing is to divide by each factor as you find it, so that you only ever reach all the way to sqrt(n) if n is prime. In this way you can factorise 2^31 with 31 trial divisions, whereas 2^31-1 takes about 2^16 trial divisions (or fewer once you start skipping even numbers after 2, etc).

Steve Jessop 2010-02-19 21:21:38

@Steve: Actually, the suggested algorithm tries only primes, so you'd be testing a few thousand, not tens of thousands candidates. But as stated it's wrong: it does find that 7 divides 49, _but not how often_. The two suggestions combined do work, e.g. 147 => 2^0 * 147 => 2^0 * 3^1 * 49 = 2^0 * 3^1 * 5^0 * 49 = 2^0 * 3^1 * 5^0 * 7^1 * 7 = 2^0 * 3^1 * 5^0 * 7^2 (4 and 6 are skipped because they're not primes)

MSalters 2010-02-22 10:44:20

@MSalters: fair point, I missed that. Calculating all prime numbers up to sqrt(n) for arbitrary n is left as an exercise for the reader, but that's where fixed-size types come in handy.

Steve Jessop 2010-02-25 00:25:31

ansaurus

tags:

views:

answers:

For a given number N i have to find all the prime numbers it's consisting of

related questions