L'impression des nombres premiers en Java en utilisant la récursivité

J'ai écrit une fonction similaire dans C, et a été en mesure d'atteindre le résultat requis contrairement à java.
Ci-dessous le code qui vérifie si un nombre est premier de manière récursive.
Compilation dit, je suis absent de l'instruction return.
Le nombre à vérifier si une prime est x. La variable i est le diviseur.(ie) x/2, (x/2)-1,...0.

public int primes(int x, int i)
{
    if(i==0)
        return 1;
    if(x%i==0)
        return 0;
    else
        primes(x, i-1);
}

Quelle est la complexité de ce code si je devais imprimer les 1000 premiers nombres premiers.

Pour la complexité, dans le pire des cas i diminue jusqu'à 0, donc si i commence à x/2, c'est environ O(x). Mais ce sera amorti à quelque chose de beaucoup plus petit car de toute évidence pas chaque nombre est premier (en.wikipedia.org/wiki/Prime_number_theorem). Pour un simple 1000 nombres premiers, je doute qu'il va prendre très longtemps de toute façon.
non, il ne sera pas amortir à rien de plus petit parce que le test est fait dans le mauvais ordre. n=1000 premiers moyens ~ N=8000 numéros de tester, par un O(N^2) algorithme; n'en soyez pas si sûr qu'il va courir vite tout simplement parce que n=1000 semble petit (vous l'avez bien dit "de toute façon"...) - sa complexité est atroce (voir, par exemple, cette Haskell entrée de test avec l'équivalent de l'algorithme montrant ~ N^2.2 , ~ n^2.5 comportement.
J'ai eu des OP primes est O(x) (ou O(n) ou quoi que ce soit). Alors bien sûr, si il boucle c'est O(n^2), mais il ne va pas prendre l'absolu pire des cas en raison de l'OP a déclaré qu'il commence i à x/2, donc evens échoue immédiatement. Alors à trouver les 1000 premiers x juste besoin d'être 7919, de sorte que les nombres premiers n'est pas récursif très loin pour la plupart des numéros.
ils ne parlent agit de trouver des 1000 premiers nombres premiers. et je vous ai donné la preuve que c'est pire que N^2.
le empiriques commandes de croissance de votre algorithme est ~ n^2.5, n en produit de nombres premiers.

InformationsquelleAutor Farveaz | 2014-07-22

6

Dans ce cas:
```
else
    primes(x, i-1);
```
Vous n'êtes pas de retourner quoi que ce soit. Cependant, le compilateur doit veiller à ce que quelque chose est retourné dans tous les cas. Juste retour quelle que soit la méthode récursive retours d'appel:
```
else
    return primes(x, i-1);
```
Également, de modifier le premier cas, la condition de i == 1 on en revient donc 1 sur les premiers correctement.
- Fonctionne comme un charme. La conversion de C à Java était le coupable!
InformationsquelleAutor rgettman
1

Au premier coup d'œil, il semble que vous êtes absent de retour dans votre instruction else:
```
public int primes(int x, int i)
{
    if(i==1)
        return 1;
    if(x%i==0)
        return 0;
    else
        return primes(x, i-1);
}
```
edit: Aussi, comme il est dit dans rgettman réponse, il y a une logique bug dans la première conditionnelle if(i==0). Il devrait être if(i==1). Après avoir testé le code ci-dessus, de modifier voici mon résultat:
```
List of primes under 100: 
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
```
InformationsquelleAutor Christian Wilkie
0

Vous avez juste besoin d'un return à l'intérieur de votre else.
```
else
    return primes(x, i-1);
```
La return il sera de retour les résultats des appels récursifs, et qu'ils vont travailler leur chemin jusqu'à la pile. Cependant, cela pourrait conduire à StackOverflowExceptions.

InformationsquelleAutor krillgar

import java.util.Scanner;

public class Primenumm {
     public static void main(String[] args) {
          System.out.println("Enter the Number :-");
          Scanner s = new Scanner(System.in);
          int limit = s.nextInt();
          for (int i = limit; i >= 1; i--) {
               if (primes(i, i - 1) == 1) {
                    System.out.println(i + " is a prime no");
               } else {
                    System.out.println(i + " is not a prime no");
               }
          }
     }

     private static int primes(int x, int i) {
          if (i == 1) {
               return 1;
          }
          try {
               if (x % i == 0) {
                    return 0;
               } else {
                    return primes(x, i - 1);
               }
          } catch (Exception e) {
               return 1;
          }
     }
}

InformationsquelleAutor Tanvir Arafat

Vous pouvez appliquer la logique:

for (i = 1; i <= 100; i++) {              
    int counter=0;    
    for (num = i; num>=1; num--) {
        if (i%num==0) {
            counter = counter + 1;
        }
    }
    if (counter == 2) {
        //Appended the Prime number to the String
        primeNumbers = primeNumbers + i + " ";
    }   
}

Puis de les afficher primeNumbers.

InformationsquelleAutor kirti

-1

public class PrintPrime {

    public static void main(String args[]) {
        for (int i = 2; i < 1000; i++) {
            primes(i, Math.ceil(Math.sqrt(i)));

        }
    }

    public static int primes(int x, double i) {
        if (i == 1)
            System.out.println(x);
        if (x % i == 0)
            return 0;
        else
            return primes(x, i - 1);
    }

}

InformationsquelleAutor dummy

-1

import java.util.Scanner;
public class Primenumm {

static int limit,flag;

public static void main(String[] args) {
    //TODO Auto-generated method stub

    System.out.println("Enter the Number :-");
    Scanner s=new Scanner(System.in);
    limit=s.nextInt();
    int i=0,j=limit;
    printNum(i,j);
}

private static int  printNum(int i, int j) {
    //TODO Auto-generated method stub

    if(j==0){
        return 1;
    }
    if(i%j==0){
        return  0;
    }
    else{

        return  printNum(i,j-1);
    }
}

InformationsquelleAutor user8492094

Vous devez vous connecter pour publier un commentaire.