Inductive logic programming (ILP)-based concept discovery systems lack computational efficiency due to the evaluation of the large search spaces they build. One way to tackle this issue is employing pruning mechanisms. In this work, we propose a two-phase pruning mechanism for concept discovery systems that employ an Apriori-like refinement operator and evaluate the goodness of the concept descriptors based on their support value. The first step, which is novel in this work, is computationally inexpensive and prunes the search space based on the coverages of the concept descriptors. The second step employs a widely employed pruning mechanism based on the support value of the concept descriptors. The experimental results show that the first step leaves a search space reduced by 4-22% to be evaluated by the second step, which is more costly.