Liczby pierwsze rekurencyjnie

Question

Dobra, muszę się spytać w kwestii jednego zadania:

Napisz funkcję, która w sposób rekurencyjny sprawdza, czy dana liczba jest liczbą pierwszą. Funkcja powinna przyjąć liczbę, którą ma sprawdzić i dzielnik, dla którego ma sprawdzić podzielność. Funkcja ma zwrócić 1, jeżeli a jest liczbą pierwszą, 0 w przeciwnym wypadku.

int is_prime_rec(int, int);

Napisz program, który wyświetla wszystkie liczby pierwsze w zadanym przedziale <x1, x2>, wprowadzonym z klawiatury. W przypadku podania przez użytkownika przedziału w którym nie ma liczb pierwszych, program powinien wyświetlić komunikat Nothing to show i zwrócić wartość 2, a w przypadku wprowadzenia błędnych danych wyświetlić komunikat Incorrect input i niezwłocznie zakończyć działanie z kodem błędu 1.

Uwaga W programie nie wolno używać zmiennych globalnych.

Uwaga W programie nie wolno używać słowa kluczowego static.

Uwaga W programie nie wolno używać pętli.

Przykładowe wejście:

podaj x1: 4
podaj x2: 10

Przykładowe wyjście:

5 7

 

Kiedyś już rozpisywałem to zadanie iteracyjnie, tutaj też podeślę swój kod:

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

/* run this program using the console pauser or add your own getch, system("pause") or input loop */
int is_prime(int a);
int main(int argc, char *argv[]) 
{
	int suma=0;
	int i;
	int a;
	int x1,x2;
	printf("Podaj poczatkowy zakres:");
	if(scanf("%d",&x1)!=1)
	{
		printf("Incorrect input");
		return 1;
	}
	printf("Podaj koncowy zakres:");
	if(scanf("%d",&x2)!=1)
	{
		printf("Incorrect input");
		return 1;
	}
	if(x2<x1)
	{
		printf("Incorrect input");
		return 1;
	}
	for(i=x1;i<=x2;i++)
	{
		a=i;
		is_prime(a);
		if(is_prime(a)==1)
		{
			suma++;
			printf("%d ",a);
		}
	}
	if(suma==0)
	{
		printf("Nothing to show");
	}
	return 0;
}
int is_prime(int a)
{
	int j;
	int kontrola=0;
	for(j=a;j>=1;j--)
	{
		if(a%j == 0)
		{
			kontrola++;
		}
		
    if(j==1 && kontrola==2)
	{
	return 1;
	}	  
	}
	return 0;
}

Kwestia teraz tego, aby przerobić to rekurencyjnie. Pytanie tylko jak to zrobić?  

Answer 1

Dam ci kilka podpowiedzi:
1. Aby sprawdzić, czy liczba jest pierwsza musisz wywołać funkcję is_prime_rec(liczba, 2)
2. Wywołanie is_prime_rec(liczba, liczba) powinno zwrócić 1

Comments

Cześć, udało mi się jako to rozpisać, ale napotkałem na kilka problemów.

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

/* run this program using the console pauser or add your own getch, system("pause") or input loop */
int is_prime_rec(int a, int b);
int wyswietlanie_pierwszych(int x1,int x2);
int main(int argc, char *argv[]) 
{
    int suma;
	int x1,x2;
	printf("Podaj poczatkowy zakres:");
	if(scanf("%d",&x1)!=1)
	{
		printf("Incorrect input");
		return 1;
	}
	printf("Podaj koncowy zakres:");
	if(scanf("%d",&x2)!=1)
	{
		printf("Incorrect input");
		return 1;
	}
	if(x2<x1)
	{
		printf("Incorrect input");
		return 1;
	}
    suma=wyswietlanie_pierwszych(x1,x2);
    if(suma==0)
    {
    	printf("Nothing to show");
	}

    return 0;
}
int wyswietlanie_pierwszych(int x1,int x2)
{
	if(x1>x2)
	{
		return 0;
	}
	if(x1<=x2)
	{
		if(is_prime_rec(x1,2)==1)
		{
		printf("%d ",x1);
		} 
		return wyswietlanie_pierwszych(x1+1,x2);
	}
	return 0;
	
}
int is_prime_rec(int a, int b)
{
	if(a<2 ||  b<2 )
	{
		return 0;
	}
	if(a==b)
	{
		return 1;
	}
	if(a%b!=0 && b<a)
	{
		return is_prime_rec(a,b+1);
	}
	if(a%b==0 && b<a)
	{
		return 0;
	}
	return 0;
}

Po pierwsze na testach funkcja is_prime_rec nie przechodzi 4 na 10 testów. Tutaj daje te testy:

   int a = is_prime_rec(2, 1);
                test_error(a == 1, "Funkcja is_prime_rec() powinna zwrócić 1, a zwróciła 0", a);
                printf("#####END#####");
        
            

          printf("#####START#####");
                int a = is_prime_rec(4, 3);
                test_error(a == 0, "Funkcja is_prime_rec() powinna zwrócić 0, a zwróciła 1", a);
                printf("#####END#####");
        

        printf("#####START#####");
                int a = is_prime_rec(3406, 3405);
                test_error(a == 0, "Funkcja is_prime_rec() powinna zwrócić 0, a zwróciła 1", a);
                printf("#####END#####");
        

Ponadto nie mogę w programie używać pętli. Próbowałem być cwany i zastosować z dodatkową funkcją rekurencyjne przechodzenie po zakresie <x1;x2> , ale oczywiście na testach wyszło "Funkcja nie powinna nic wyświetlać". Jak rozwiązać powyższe problemy?  :/

---

Troszkę przekombinowałeś w funkcji is_prime_rec. Wystarczą ci w niej tylko dwa proste warunki logiczne (bez żadnych spójników AND/OR)

int is_prime_rec(int a, int b) {
    if (a==b)
        return 1;
    if ( kiedy na pewno nie jest pierwsza )
        return 0;
    return is_prime_rec(a, b+1);
}

Jeżeli funkcja wyswietlanie_pierwszych nie może wyświetlać nic na ekranie to nie wiem jak ci pomóc z drugim problemem.

---

Dobra, zadanie poszło i zostało mi zaliczone. Dziękuję za pomoc. :)