Primary Key and autonumber

Let's assume I have a database that has 1 million records, all uniquely identified with a Primary Key.
If my database does not provide an Autonumber for the Primary Key, how can I efficiently give each new record a unique key without going through the entire database to check if that value has already been taken?

Francois Received on Wed Jan 05 2000 - 00:00:00 CST