Il y a quelque temps, j'ai eu un problème qui ressemblait à ceci:

Un nombre chanceux est un nombre où la somme des nombres avant lui (y compris lui-même) est premier. Par exemple, deux est un nombre chanceux car il devient 1 + 2. Comme il s'agit de 3 et que 3 est un nombre premier, nous pouvons conclure que 2 est un nombre chanceux.

J'ai essayé de construire un code simple pour trouver quelques nombres chanceux

public static void main(String args[]) {
    boolean isPrime = true;
    for(int x = 3; x < 1000; x++) {
        int num = ( (x * (x + 1)) / 2);
        // formula for checking the sum of integers one through x
        for(int i = 2; i < num; i++) {
            if(num % i == 0) {
                isPrime = false;
                // if it's false it is not prime
            }
            if(isPrime == true) {
                System.out.println(x);
                // prints out the original number, the sum of the numbers before it is a prime number
            }
        }
    }
}

En d'autres termes, il devrait prendre un nombre, x, le brancher dans la formule et voir si le nombre retourné par la formule est un nombre premier. Cependant, j'obtiens de longues chaînes de nombres qui ne sont pas premiers (comme 3, 4, 5, 6, 7 ...).

0
EggPie 26 janv. 2017 à 08:27

4 réponses

Meilleure réponse

Juste un petit problème logique. Vous devriez imprimer un prime quand c'est un premier dans l'acte. Cela signifie qu'il ne se divise pas par tous ces chiffres. Alors déplacez-le en dehors de la boucle.

for(int x = 3; x < 1000; x++) {

    int num = ( (x * (x + 1)) / 2);
    // formula for checking the sum of integers one through x

    if (num%2 == 0) {
        isPrime = false;
    }

    for(int i = 3; isPrime && i < num ; i += 2) {

        if(num % i == 0) {
            isPrime = false;
            // if it's false it is not prime
        }
    }

    if(isPrime == true) {
        System.out.println(x);
        // prints out the original number, the sum of the numbers before it is a prime number
    }
}

J'ai également ajouté une optimisation - pas besoin de vérifier si n% 4, n% 6 itd est égal à 0, quand ce n'est pas égal, ainsi que de vérifier si se divise par un grand nombre quand déjà trouvé un diviseur.

En revanche, c'est impossible pour x > 2. Le seul x pour lequel cela fonctionne est 2.

1
xenteros 26 janv. 2017 à 05:54

La somme des entiers de 1 à x est x * (x + 1) / 2.

Soit x soit x + 1 est pair, donc la somme est toujours le produit de 2 entiers - soit x * ((x + 1) / 2) ou (x / 2) * (x + 1).

Un nombre premier ne peut pas être fait comme le produit de deux entiers à moins que ces deux entiers soient 1 et lui-même, donc, si x est "chanceux", alors soit (x + 1) / 2 == 1 ou x / 2 == 1 ou x + 1 == 1 ou x == 1, c'est-à-dire que x vaut 0, 1 ou 2.

Puisque 0 ne compte pas ...

1 et 2 sont les seuls nombres chanceux

4
Matt Timmermans 26 janv. 2017 à 05:54

C'est impossible. Mais voici ma solution utilisant des flux !!

public class Main {

    public static void main(String[] args) {
        System.out.println(
                IntStream.range(2, 1000000)
                         .map(e->factor(e))
                         .filter(e -> isPrime(e))
                         .boxed()
                         .collect(Collectors.toCollection(ArrayList::new))
                );

    }

    public static boolean isPrime(int input) {
        for (int i=2;i<input;i++) {
            if (input%i==0) {
                return false;
            }
        }
        return true;
    }

    public static int factor(int input) {
        return ( (input * (input + 1)) / 2);

    }
}
0
Nick Ziebert 26 janv. 2017 à 06:02

À chaque étape de votre boucle for interne, vous vérifiez si elle est optimale. Parce qu'il est par défaut premier, s'il n'est pas trouvé, il n'est pas premier lors du premier contrôle qu'il affiche.

public static void main(String args[]) {

  boolean isPrime = true;

  for (int x = 3; x < 1000; x++) {

   int num = ((x * (x + 1)) / 2);
   // formula for checking the sum of integers one through x

   for (int i = 2; i < num; i++) {

    if (num % i == 0) {
     isPrime = false;
     // if it's false it is not prime
    }
  }

    if (isPrime == true) { 
     System.out.println(x);
     // prints out the original number, the sum of the numbers before it is a prime number
    }

  }
0
pfg 26 janv. 2017 à 05:45