американцы, говорите, тупые...

Задали написать программу для нахождения простых чисел. Что-то я сидел, сидел и только одно на ум пришло: если число не делится на 2, 3, 5 и sqrt(это_число), то это простое число. Верно? Или я допустил ошибку? В любом случае, как реализовать это, скажем на Си?
Спасибо.

откровение

Сегодня сидим пьём чай на веранде; немец по приколу говорит: "нас, немцев, очень много, we rule the world" - тут вмешивается китайская девочка шести лет, и говорит: "we rule the world!" - её спрашивают, о ком это она, отвечает: "Chinese!"