Projet Euler prob. 3 IndexOutOfBoundsException

Question

J'essaie d'utiliser une méthode Sieve of Eratosthenes pour trouver le plus grand facteur premier d'un grand nombre (problème 3 dans le projet Euler).

Ma syntaxe semble être correcte, et j'utilise Long (pas int), mais je reçois le message d'erreur suivant:

Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 1, Size: 1 
    at java.util.ArrayList.rangeCheck(Unknown Source) 
    at java.util.ArrayList.get(Unknown Source) 
    at problem3.ProblemThree.Factor(ProblemThree.java:49) 
    at problem3.ProblemThree.Recursion(ProblemThree.java:37) 
    at problem3.ProblemThree.main(ProblemThree.java:83) 

Je ne sais pas pourquoi cela se passe. Quelqu'un pourrait-il me dire ce que je fais de mal ici?

package problem3; 

import java.util.List; 
import java.util.ArrayList; 

public class ProblemThree 
{ 
    //initializing variables and lists 
    long factorNo; 
    long nowTesting; 
    int i; 
    List<Long> allPrimeList = new ArrayList<Long>(); 
    List<Long> ourPrimes = new ArrayList<Long>(); 

    ProblemThree(long x) //constructor; the input "x" is the number whose highest prime factor is being sought 
    { 
     factorNo = x;  
    }  

    void initialize() //use the workaround initialization (add 2 to the allPrimesList, set nowTesting to 3). 
         //If the factorNo is even, add 2 to the primes list 
         //TODO: need more elegant solution 
    { 
     allPrimeList.add((long) 2); 
     nowTesting=3; 
     if(factorNo % 2 == 0) ourPrimes.add((long) 2); 
     i = 0; 
    }   

    void recursion() //keep factoring the next nowTesting until the next nowTesting is greater than half of the factorNo 
    { 
     while (nowTesting <= (factorNo/2)) 
     { 
      nowTesting = factor(nowTesting); 
     } 
     System.out.println(ourPrimes); 
    } 

    long factor(long t) //The factorization algorithm. Lists all the factors of long t 
    { 
     nowTesting = t; 

// Line 49: 
    if ((nowTesting % allPrimeList.get(i)) == 0) 
     { 
      i = 0; 
      return (nowTesting + 2);    
     } 
     else 
      if(i <= allPrimeList.size()) //if we have not yet reached the end of ourPrimeList 
      { 
       i++; 
       return nowTesting; 
      } 
      else //if the end of ourPrimeList has been reached without a single modulus==0, this number is a prime 
      { 
       allPrimeList.add(nowTesting); 

       if(factorNo%nowTesting==0) //if the nowTesting is a prime factor of factorNo, it will be perfectly divisible 
       { 
        ourPrimes.add(nowTesting); 
       }      
       i=0; 
       return (nowTesting+2); 
      }    
    } 

    public static void main (String[] args) 
    { 
     ProblemThree pt = new ProblemThree(600851475143L); 
     pt.initialize(); 
     pt.recursion(); 
    } 
} 

Answer 1

Une approche intéressante. Bien sûr, personne ne devrait résoudre vos problèmes d'Euler. Mais saviez-vous que la deuxième fois, vous entrez «facteur» maintenantTesting est 3?

// The factorization algorithm. Lists all the factors of long t 
long factor (final long nowTesting) 
{ 
    System.out.println ("entering factor: " + nowTesting); 

idées mineures:

allPrimeList.add ((long) 2); 

peut être écrit:

allPrimeList.add (2L); 

et vous reconnaissiez pobably la "finale" en face du paramètre 'long' en facteur? Il aide à raisonner sur le code, si vous marquez tout ce qui n'est pas changé final. En pratique, la conséquence est que votre Javacode est encombré de modificateurs «finaux», mais c'est comme ça. C'est un signe de bon code - peut-être pas de bon design. La finale aurait pu être la valeur par défaut.

Answer 2

À la ligne 49, ne devriez-vous pas vérifier si nowTesting est divisible par i, et non l'élément ith de allPrimes?

Answer 3

vous remercie tous pour patauger patiemment mon code, je me rends compte qu'il doit avoir été atrocement douloureux :)

Je viens de résoudre le problème. Mon approche précédente semble très compliquée rétrospectivement. C'est la solution finale que j'ai utilisée, un peu plus élégante, bien qu'elle puisse encore être améliorée:

//second attempt from the ground up! 
package problem3; 


public class BiggestPrime 
{ 
    long lInput; 
    long factorTest; 
    long currentHeight; 
    boolean divided; 

    public BiggestPrime(long n) 
    { 
     factorTest = 2; 
     currentHeight = n; 

     System.out.println("The prime factors of " + n + " are:"); 

     while (factorTest<currentHeight) 
     { 
      if (divided == true) {factorTest = 2; divided = false;} 
      if (factorTest > currentHeight) {System.out.println("factorTest is greater than currentHeight; breaking"); break;} 
      if (currentHeight%factorTest==0) 
      { 
       System.out.println(factorTest); 
       currentHeight /= factorTest; 
       divided = true; 
      } 
      else { factorTest = factorTest + 1L; divided = false;} 
     } 
     if (factorTest == currentHeight) 
     { 
      System.out.println(factorTest); 
     } 
     System.out.println("The end"); 

    } 


    public static void main (String[] args) 
    { 
     BiggestPrime bp = new BiggestPrime(600851475143L); 
    } 

}