Generating Prime Factors

Let us denote the Set of Prime Factors by X = {(n,f)} where n is integer and f is a set of prime numbers that makes up n by multiplication.

Multiplying the set X, upto N by an integer z = w^u is defined as z.X = {z.(n,f)} = {(z.n, f union w)} where w is prime, u is a positive integer and z.n <= N.

z.(n,f) returns void, if z.n > N.

generate_prime_factors(P, N) // P is the set of prime numbers upto N, N is a positive integer
{

initialize a Set of Prime Factors, X = {(1,{1})}

for all the prime numbers i in the set P in ascending order do
j= 1;
while i^j <= N do
Y = i^j.X;
X = X union Y;
j++;
end while
end for
return X

}


let us find the prime factorization of all the numbers upto N = 10:

inital state:
X = {(1,{1})}

step1: i = 2, j = 1
Y = 2.X ={(2,{1,2})}
X = X union Y = {(1,{1}), (2,{1,2})}

step2: i = 2, j=2
Y = 2^2.X = {(4,{1,2}), (8,{1,2})}
X = X union Y = {(1,{1}), (2,{1,2}), (4,{1,2}), (8,{1,2})}

step3:i = 2, j = 3
Y = 2^3.X = {(8,{1,2})}
X = X union Y = {(1,{1}), (2,{1,2}), (4,{1,2}), (8,{1,2})}

step4: i = 2, j = 4; i^j = 2^4 = 16 > N = 10
do nothing


step5: i = 3, j = 1
Y = 3.X = {(3,{1,3}), (6,{1,2,3})}
X = X union Y = {(1,{1}), (2,{1,2}), (3,{1,3}), (4,{1,2}), (6,{1,2,3}), (8,{1,2})}

step6: i = 3, j = 2
Y = 3^2.X = {(9,{1,3})}
X = X union Y = {(1,{1}), (2,{1,2}), (3,{1,3}), (4,{1,2}), (6,{1,2,3}), (8,{1,2}), (9,{1,3})}


step7: i = 3, j =3; 3^3 > 10
do nothing

step8: i = 5, j = 1
Y = 5.X = {(5,{1,5}), (10,{1,2,5})}
X = X union Y = {(1,{1}), (2,{1,2}), (3,{1,3}), (4,{1,2}), (5,{1,5}), (6,{1,2,3}), (8,{1,2}), (9,{1,3}), (10,{1,2,5})}


step9: i = 5, j = 2; 5^2 = 25
do nothing

step9: i = 7, j = 1
Y = 5.X = {(7,{1,7})}
X = X union Y = {(1,{1}), (2,{1,2}), (3,{1,3}), (4,{1,2}), (5,{1,5}), (6,{1,2,3}), (7,{1,7}), (8,{1,2}), (9,{1,3}), (10,{1,2,5})}