how can I find out the prime numbers in given integers in PHP?

Gary_King

thanks in advance!

laserlight

hmm... could you re-phrase that?

Do you want to know of ways to test the primality of a given integer, to search for primes within a given range, or to factor an integer into its prime factors?

Gary_King

for instance, the following numbers I want to be able to grab their prime numbers:

INPUT
24
348
124985

OUTPUT (primes)
2223
22329
573571

thanks! 🙂

laserlight

You're looking to perform prime factorisation of integers, search the Web for more information.

A simplistic algorithm would be to use an existing list of primes up to the square root of the integer.
Iterate over this list, dividing the integer and setting the integer to be the quotient obtained whenever division may be performed perfectly.
Once a remainder will be obtained, move to the next prime in the list.
Once the list is exhausted, whatever primes used in perfect division and the final value of the integer are the prime factors.

Gary_King

Can you suggest an algorithm or some code to use? Like, a function for instance?

laserlight

I already suggested an algorithm in my previous post.

Gary_King

Could you help me write some pseudo-code? 🙁

laserlight

hmm... not sure if this is correct but...

let num be the integer to be factorised

set max = integer square root of num
set prime_list = list of primes in range [2, num]
foreach prime_list as prime
	while num % prime == 0
		print prime
		num = num / prime
print num