Win a copy of Penetration Testing Basics this week in the Security forum!

# Finding all factors from the list of prime factors.

Nitish Bangera
Ranch Hand
Posts: 537
Well, this is kind of confusing me to find out all factors of a number using the list of primes. The primes can be combined is all possible combination to get the other factors of the number. But, some of the factors are missing it numbers which are high like 4095 and more. My code for getting prime factors is

and combining the primes is

Campbell Ritchie
Sheriff
Posts: 50624
82
If you have a List of primes, you might do well to serialise it for future reference; why calculate the primes anew every time?
How about using a sieve of Eratosthenes, then populating your list of primes, then you can iterate through the List of numbers, and for an example like 4095 (3 × 3 × 5 × 7 × 13) you can calculate the factors very easily.
Use a pencil and paper and work out the prime factors of such a number: go through the method on paper then write down exactly how you did it. Then you have some pseudocode and you can easily convert that to real code. I think you are correctly checking for prime factors. How did you validate your isPrime() method? What you have written, with 8 unidentifiable local variables, looks very complicated.

Nitish Bangera
Ranch Hand
Posts: 537
Well isPrime is easy. check the number divisibility with i = 0 to i < squareroot of the number. Well that is understood. Well what i have wrritten is a kind of pseudocode only. l1 is a set whereas l has the primes. The method i thought is

eg:- 4095 = 3^2 * 5^1 *7^1 * 13^1. So 3^0 5^0 7^0 13^0, then 3^0 5^1 7^1 13^1 the 3^1 5^0 7^0 13^0 and so on for every number 5(0,1),7(0,1) and 13(0,1).

On paper every possible combination is calculated. But to convert it to an implementation is kind of giving me a problem.

Campbell Ritchie
Sheriff
Posts: 50624
82
You implement what you would do on paper. I have already said you appear to be checking whether a number divides by something. But your prime numbers method is still incomprehensible. You appear to be confusing sets an lists; the two are very different.

I still think using a sieve of Eratosthenes to create a set of prime numbers which can be reused is a better approach.