Форум » C/C++ для начинающих (C/C++ for beginners) » C-функция, определяющая, является ли целое число простым. » Ответить
C-функция, определяющая, является ли целое число простым.
Сыроежка: Эта тема создана на основе вопроса на Stackoverflow C program to take integer if it is Prime or Not Prime и связана с тем, как написать C-функцию, определяющую, является ли целочисленное число простым. Глядя, как реализована такая функция в ответах к указанному вопросу, создается впечатление, что даже написание такой функции вызывает у многих программистов трудности. Вот пара примеров реализации этой функции, присутствующей в ответах. [pre2] int isprime(long n) { for (long i = 2; i != n; ++i) if (n%i == 0) return 0; return 1; } [/pre2] [pre2] int isprime(long n) { if(n > 1 && n <= 3) return 1; if(abs(n) == 1) return 0; if(n%2 == 0) return 0; for (long i = 3; i <= sqrt(n); i += 2) if (n%i == 0) return 0; return 1; } [/pre2] Первая реализация этой функции вообще некорректна, так как для чисел 0 и 1, которые не являются простыми, цикл имеет неопределенное поведение. Аналогично поведение цикла для отрицательных аргументов функции. И вторая реализация функции неверная. Во-первых, для чисел типа long int следует вызывать функцию labs вместо функции abs. Во-вторых, отрицательные числа за исключением числа -1 также попадают в категорию простых чисел. К тому же функция слишком усложнена и имеет аж 5(!) предложений return. И в любом случае возникает вопрос: а что делать, если нужно определить, является ли число, например, типа unsigned long int или long long int или unsigned long long int простым? Писать для каждого из этих типов отдельную функцию, выдумывая для нее новое имя, так как в C отсутствует перегрузка функций? Так, как правильно написать реализацию функции, определяющую, является ли целое число простым? Во-первых, отметим, что понятие простого числа вводится для чисел натурального ряда. Поэтому параметр функции следует сделать беззнаковым целым типом. Во-вторых, следует выбрать максимальный беззнаковый целый тип такой, как, например, unsigned long long int. Тогда такую функцию можно вызывать для аргумента любого беззнакового целочисленного типа. Теперь рассмотрим вопрос: какой тип следует назначить для возвращаемого значения функции. Можно было бы использовать тип _Bool. Но тогда такую функцию нельзя будет использовать в проекте на базе языка C++, так как в C++ такой целочисленный тип отсутствует. Поэтому тип возвращаемого значения лучше задать тип int. Ниже приведена демонстрационная программа, показывающая реализацию и использование функции, определяющей, является ли целое число простым. [pre2] #include <stdio.h> int isprime( unsigned long long int x ) { int prime = x % 2 == 0 ? x == 2 : x != 1; for ( unsigned long long int i = 3; prime && i <= x / i; i += 2 ) { prime = x % i != 0; } return prime; } int main( void ) { const int N = 100; for ( int i = 0; i < N; i++ ) { if ( isprime( i ) ) printf( "%d ", i );; } putchar( '\n' ); }[/pre2] Вывод программы на консоль: [pre2] 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97[/pre2]
Ответов - 0
полная версия страницы