Fully Homomorphic Encryption is a cryptographic scheme to prevent the privacy leakage of sensitive data. However, one challenge with FHE is the ciphertext comparison widely used in clustering, an important scheme used for data mining and analysis. In this paper, we create a series of ciphertext comparison functions by rewriting the comparison in HE-friendly operations and the Heaviside step function approximated by Chebyshev Polynomials. Furthermore, we solve the challenging ciphertext division through constructing a function whose root is the reciprocal of the divisor and applying Newton's method to ap-proximate the root. Then, we propose a fully privacy-preserving, effective and efficient clustering scheme based on our ciphertext comparison and division. Tests on various datasets show that our algorithm maintains nearly the same classification accuracy as vanilla k-means and significantly outperforms the baseline in terms of accuracy. We then optimize our scheme by batching over multiple records and multithreading, and the results show that our approach has a significant efficiency advantage. Compared with the state-of-the-art FHE-based privacy-preserving clustering scheme (SAC 2018), our algorithm is four orders of magnitude faster than theirs.