In order to reduce the capacity of the navigation star database, an algorithm for screening navigation stars on star sensors is proposed. Uniformly distributed optical random vectors on the celestial sphere are generated and used for the Monte Carlo samples. The bright stars in the circumferential field of view （FOV） determined by each optical axis vector are in turn taken as the star subsets. The stars not found in the constructing star database are added to the constructing database in these star subsets and simultaneously the duplicate stars are discarded. After traversing all the implementation samples, one can finally obtain the navigation star database. The simulation condition is set as follows. The FOV of the star sensor is 15°×15°, the limiting star magnitude is 5.6 m, the angular distance threshold between stars is 1°, and the number of navigation stars required for star map matching is 15. The navigation star database constructed by this algorithm improves the uniformity of the navigation star′s distributions. In the necessary and sufficient sense of star map matching, the number of navigation stars in the star database reach the minimum. It thus reduces the number of matching pattern databases and reduces the memory requirements, which shows the engineering and practical value for the design of star sensors.