  When people mention the number theoretical achievements in Ancient China, the
famous Chinese Remainder Theorem always springs to mind. But, two more of
them--the concept of primes and the algorithm for counting the greatest common
divisor, are rarely spoken. Some scholars even think that Ancient China has not
the concept of primes. The aim of this paper is to show that the concept of
primes in Ancient China can be traced back to the time of Confuciusor (about
500 B.C.) or more ago. This implies that the concept of primes in Ancient China
is much earlier than the concept of primes in Euclid's \emph{Elements}(about
300 B.C.) of Ancient Greece. We also shows that the algorithm for counting the
greatest common divisor in Ancient China is essentially the Euclidean algorithm
or the binary gcd algorithm. Donald E. Knuth said that "the binary gcd
algorithm was discovered by J. Stein in 1961". Nevertheless, Knuth was wrong.
The ancient Chinese algorithm is clearly much earlier than J. Stein's
algorithm.
