Рекурсия в си

[Life]

помогите пожалуйста кто чем может как написать программу на си
Написать рекурсивную функцию, определяющую, является ли заданное натуральное число простым (простым называется натуральное число, большее 1, не имеющее других делителей, кроме единицы и..

[bayandin]

На одном известном ресурсе говорится, что

Цитата:

The prime numbers can be defined as consisting of:
-2, the smallest prime;
-each positive integer which is not evenly divisible by any of the primes smaller than itself.
The integer 2 is our base case; checking the primality of any larger integer X requires us to know the primality of every integer between X and 2, but each such integer is closer to our base case of 2 than X is.

Думаю, можно алгоритм основывать на этом.

[architect]

Непонятно, насколько совершенным должно быть решение. Если в лоб - то рекурсивная функция должна вызывать саму себя с двумя параметрами: исходное делимое и текущий делитель. Величина возврата - остаток от деления делимого на делитель. Условие рекурсивного вызова - делитель меньше делимого более чем в 2 раза. Условие прекращения рекурсии - делитель больше или равен половине делимого.

Оптимизация заключается в эффективности генерации делителей - самый эффективный метод, это реализация алгоритма (одного из) генерации простых чисел. Самый неэффективный (и простой) - последовательный инкрементальный перебор кандидатов в делители.