A graph G is considered to have a prime labeling when each of its |V| vertices is assigned a unique label from the set {1, 2, 3, 4, …,|V|}, ensuring that the labels of any two connected vertices are coprime. In 1980, Roger Entringer proposed the conjecture that ``All trees have a Prime labeling”, which is not settled till today. In spite of many researchers working on prime labeling, conjecture on prime trees is still open. Up to our knowledge, no one has given an algorithm to generate prime trees. In this paper, given an arbitrary tree T, we develop an algorithm to construct a prime labeled tree T’ such that T is a subtree of T’. We extend this algorithm for k arbitrary trees Ti, where i = 1, 2, 3, …, k to construct a larger prime labeled tree T’ such that each Ti is a subtree of T’. We also develop a log-linear algorithm to construct a larger prime labeled tree T’ from k prime trees Ti, where i = 1, 2, 3, …, k such that Ti is a subtree of T’. Further, we prove the correctness of the proposed algorithms and obtain the time complexity of the proposed algorithms.