C Программа, которая определяет, является ли число простым или нет, используя рекурсивную функцию.

Question

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

#include <stdio.h>
//function for determining whether a number is prime or not
int isprime(int i, int n){
    i = 2; 
    if(n > 1){
        /* i = 2, i is the divisor that checks whether n (the number
        being checked for being prime) is in fact prime */
        if(n % i == 0){
            return 1; 
        }
        /* recursive step that returns function with increased value
        of i */
        isprime(i + 1, n);
    }
    else {
        return 0;
    }
    return -1;
}

int main(){
    int x;
    //scans integer from the keyboard
    scanf("%d", &x);
    //calls recursive function 
    if(isprime(2, x) == 1){
        printf("%d is prime\n", x);
    }
    if(isprime(2, x) == 0){
        printf("%d is not prime\n", x);
    }
    return 0;
}

Последний вопрос: вызывает ли рекурсивная функция, как в моей программе:

 isprime(2, x) 

правильный синтаксис для использования? Правильно ли вставить число 2 непосредственно в аргумент функции?

Любая помощь приветствуется! :) 1009 *

Answer 1

Вот программа, которую я создал, которая распечатывает, является ли число простым или нет, используя рекурсивную функцию для определения этого! Комментарии в программе объясняют каждую часть! Надеюсь, это поможет любому, кто пытается создать подобную программу!

#include <stdio.h>
// i = divisor
// n = number being checked for being prime
int isprime(int i, int n){
    //base case one: 1 is not prime
    if (n == 1){
        return 0;
    }
    //base case two: 2 is prime 
    if (n == 2){
        return 1;
    }
    //if i is a divisor then n not prime 
    if (n % i == 0){
        return 0;
    }
    /* if root of n is reached while trying 
    to find a divisor but no divisor found, so 
    no previous return, then we have a prime number */
    if (i * i > n){
        return 1;
    }
    //recursive step, trying next value as divisor
    return isprime(i + 1, n);
}

int main(){
    int x;
    scanf("%d", &x);
    if(isprime(2, x) == 1){
        printf("%d is prime\n", x);
    }
    if(isprime(2, x) == 0){
        printf("%d is not prime\n", x);
    }
    return 0;
}

Вход для этой программы выглядит следующим образом:

3 

Выход этой программы выглядит следующим образом:

3 is prime

Answer 2

Пример программы:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int is_prime(int n, int div)
{
    if (n <= 1)
        return 0;
    else if (div <= 1)
        return 1;
    else if (n % div == 0)
        return 0;
    return is_prime(n, --div);
}

int main()
{
    for (int i = 0; i < 100; i++)
    {
        printf("%d is %s\n", i, is_prime(i, (int)(sqrt(i)))? "prime":"not prime");
    }

    return 0;
}

Два аргумента, которые вам нужно передать, это проверяемое число и его квадратный корень. Вам не нужно проверять числа, превышающие это, потому что если вы думаете об этом, в действительности нет необходимости.

Например, если ваш номер 16, вам нужно будет только проверить цифры от 1 до 4. Видтрудно объяснить, поэтому вот таблица:

1*16
2*8
4*4
8*2 <----- We already checked this!!
...

Надеюсь, это поможет!

Answer 3

Я рекомендую вам иметь дело с проверкой аргументов (отрицательный ввод) и особыми случаями (четными числами, отличными от 2) в общей функции is_prime(), но как только ваши данные будут чистыми, переведите вычисление в целевую функцию is_prime_recursive(),избегая лишних тестов:

#include <stdio.h>
#include <stdbool.h>

bool is_prime_recursive(unsigned number, unsigned odd_divisor)
{
    if (odd_divisor * odd_divisor > number) {
        return true;
    }

    if (number % odd_divisor == 0) {
        return false;
    }

    return is_prime_recursive(number, odd_divisor + 2);
}

bool is_prime(int number)
{
    if (number <= 1) {
        return false;
    }

    if (number % 2 == 0) {
        return (2 == number);
    }

    return is_prime_recursive(number, 3);
}

int main()
{
    for (int i = 0; i <= 100; i++)
    {
        printf("%d is %sprime\n", i, is_prime(i) ? "" : "not ");
    }

    return 0;
}

Answer 4

Следующий предложенный код:

1. безупречная компиляция
2. выполняет желаемую функциональность
3. проверяет и обрабатывает ошибки ввода / вывода
4. включаеткомментарии к вопросу OPs
5. полностью изменили значение возвращаемого значения 0 или 1 для простоты вычисления
6. должным образом реализует рекурсивный алгоритм, включая крайние случаи и условие остановки
7. может значительно ограничить глубину рекурсии, используя sqrt 'n' в качестве ограничивающего фактора для параметра 'i'
8. использует значения без знака, чтобы избежать осложнений отрицательных чисел

и теперь предложенный код:

#include <stdio.h>
#include <stdlib.h>


int isprime( unsigned i, unsigned n )
{
    if( n < 2 )
    { // cannot be prime
        return 1;  
    }

    if( i >= n )
        return 0;

    if(n % i == 0)
    {  // then, not prime
        return 1; 
    }

    return isprime(i + 1, n );
}

int main( void )
{
    unsigned x;
    if( scanf("%u", &x) != 1 )
    {
        fprintf( stderr, "scanf failed\n" );
        exit( EXIT_FAILURE );
    }

    // implied else, scanf successful

    if( !isprime(2, x ) )
    {
        printf("%d is prime\n", x);
    }
    else
    {
        printf("%d is not prime\n", x);
    }
    return 0;
}